# Stochastic Bias-Reduced Gradient Methods

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

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 55 references that are in the map.
- First posted on arXiv 17 Jun 2021.

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

- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Certifying Some Distributional Robustness with Principled Adversarial Training](https://mlsanity.com/paper/1710.10571/) (2017)
- [Private Stochastic Convex Optimization with Optimal Rates](https://mlsanity.com/paper/1908.09970/) (2019)
- [Large-Scale Methods for Distributionally Robust Optimization](https://mlsanity.com/paper/2010.05893/) (2020)
- [Stochastic model-based minimization of weakly convex functions](https://mlsanity.com/paper/1803.06523/) (2018)
- [Private Stochastic Convex Optimization: Optimal Rates in Linear Time](https://mlsanity.com/paper/2005.04763/) (2020)
- [Katyusha: The First Direct Acceleration of Stochastic Gradient Methods](https://mlsanity.com/paper/1603.05953/) (2016)
- [Private Stochastic Convex Optimization: Optimal Rates in ℓ1 Geometry](https://mlsanity.com/paper/2103.01516/) (2021)
- [Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent](https://mlsanity.com/paper/1407.1537/) (2014)
- [An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games and its Applications](https://mlsanity.com/paper/2004.04250/) (2020)
- [A Universal Catalyst for First-Order Optimization](https://mlsanity.com/paper/1506.02186/) (2015)
- [Tight Complexity Bounds for Optimizing Composite Objectives](https://mlsanity.com/paper/1605.08003/) (2016)
- [Acceleration with a Ball Optimization Oracle](https://mlsanity.com/paper/2003.08078/) (2020)
- [Minimizing the Maximal Loss: How and Why?](https://mlsanity.com/paper/1602.01690/) (2016)
- [Complexity of Highly Parallel Non-Smooth Convex Optimization](https://mlsanity.com/paper/1906.10655/) (2019)
- [Un-regularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimization](https://mlsanity.com/paper/1506.07512/) (2015)
- [Private Non-smooth Empirical Risk Minimization and Stochastic Convex Optimization in Subquadratic Steps](https://mlsanity.com/paper/2103.15352/) (2021)
- [On Acceleration with Noise-Corrupted Gradients](https://mlsanity.com/paper/1805.12591/) (2018)
- [Unbiased Multilevel Monte Carlo: Stochastic Optimization, Steady-state Simulation, Quantiles, and Other Applications](https://mlsanity.com/paper/1904.09929/) (2019)
- [Lower Bounds for Parallel and Randomized Convex Optimization](https://mlsanity.com/paper/1811.01903/) (2018)
- [Projection Efficient Subgradient Method and Optimal Nonsmooth Frank-Wolfe Method](https://mlsanity.com/paper/2010.01848/) (2020)
- [Thinking Inside the Ball: Near-Optimal Minimization of the Maximal Loss](https://mlsanity.com/paper/2105.01778/) (2021)
- [Bundle-Level Type Methods Uniformly Optimal for Smooth and Nonsmooth Convex Optimization](https://mlsanity.com/paper/1309.5547/) (2013)
- [Gradient Sliding for Composite Optimization](https://mlsanity.com/paper/1406.0919/) (2014)
- [Semi-supervised Learning based on Distributionally Robust Optimization](https://mlsanity.com/paper/1702.08848/) (2017)
- [The proximal point method revisited](https://mlsanity.com/paper/1712.06038/) (2017)
- [Unified Acceleration of High-Order Algorithms under H"older Continuity and Uniform Convexity](https://mlsanity.com/paper/1906.00582/) (2019)

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

- [Adapting to Mixing Time in Stochastic Optimization with Markovian Data](https://mlsanity.com/paper/2202.04428/) (2022)
- [Bring Your Own Algorithm for Optimal Differentially Private Stochastic Minimax Optimization](https://mlsanity.com/paper/2206.00363/) (2022)
- [Near-Optimal Algorithms for Making the Gradient Small in Stochastic Minimax Optimization](https://mlsanity.com/paper/2208.05925/) (2022)
- [ReSQueing Parallel and Private Stochastic Convex Optimization](https://mlsanity.com/paper/2301.00457/) (2023)
- [Distributionally Robust Optimization via Ball Oracle Acceleration](https://mlsanity.com/paper/2203.13225/) (2022)
- [Contextual Stochastic Bilevel Optimization](https://mlsanity.com/paper/2310.18535/) (2023)
- [Optimal Multi-Distribution Learning](https://mlsanity.com/paper/2312.05134/) (2023)
- [RECAPP: Crafting a More Efficient Catalyst for Convex Optimization](https://mlsanity.com/paper/2206.08627/) (2022)
- [Mirror Descent Algorithms with Nearly Dimension-Independent Rates for Differentially-Private Stochastic Saddle-Point Problems](https://mlsanity.com/paper/2403.02912/) (2024)
- [Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductions](https://mlsanity.com/paper/2406.02789/) (2024)
- [Dynamic Byzantine-Robust Learning: Adapting to Switching Byzantine Workers](https://mlsanity.com/paper/2402.02951/) (2024)
- [Multi-level Monte-Carlo Gradient Methods for Stochastic Optimization with Biased Oracles](https://mlsanity.com/paper/2408.11084/) (2024)
- [The Ball-Proximal (="Broximal") Point Method: a New Algorithm, Convergence Theory, and Applications](https://mlsanity.com/paper/2502.02002/) (2025)
- [Multilevel neural simulation-based inference](https://mlsanity.com/paper/2506.06087/) (2025)
- [Solving Stochastic Variational Inequalities without the Bounded Variance Assumption](https://mlsanity.com/paper/2602.05531/) (2026)
- [Revisiting Inexact Fixed-Point Iterations for Min-Max Problems: Stochasticity and Structured Nonconvexity](https://mlsanity.com/paper/2402.05071/) (2024)
- [Quantum Algorithms and Lower Bounds for Finite-Sum Optimization](https://mlsanity.com/paper/2406.03006/) (2024)
- [Non-Euclidean Broximal Point Method: A Blueprint for Geometry-Aware Optimization](https://mlsanity.com/paper/2510.00823/) (2025)
- [A Whole New Ball Game: A Primal Accelerated Method for Matrix Games and Minimizing the Maximum of Smooth Functions](https://mlsanity.com/paper/2311.10886/) (2023)
- [Closing the Computational-Query Depth Gap in Parallel Stochastic Convex Optimization](https://mlsanity.com/paper/2406.07373/) (2024)
- [Differentially Private Optimization with Sparse Gradients](https://mlsanity.com/paper/2404.10881/) (2024)
- [Inference-time optimization for experiment-grounded protein ensemble generation](https://mlsanity.com/paper/2602.24007/) (2026)
- [Unbiased least squares regression via averaged stochastic gradient descent](https://mlsanity.com/paper/2406.18623/) (2024)
- [Interpreting Bias in the Neural Networks: A Peek Into Representational Similarity](https://mlsanity.com/paper/2211.07774/) (2022)
- [Fast, Parallel, Query-Efficient Binary Classification](https://mlsanity.com/paper/2607.04062/) (2026)

## Abstract (arXiv)

We develop a new primitive for stochastic optimization: a low-bias, low-cost estimator of the minimizer x_star of any Lipschitz strongly-convex function. In particular, we use a multilevel Monte-Carlo approach due to Blanchet and Glynn to turn any optimal stochastic gradient method into an estimator of x_star with bias δ, variance O(log(1/δ)), and an expected sampling cost of O(log(1/δ)) stochastic gradient evaluations. As an immediate consequence, we obtain cheap and nearly unbiased gradient estimators for the Moreau-Yoshida envelope of any Lipschitz convex function, allowing us to perform dimension-free randomized smoothing. We demonstrate the potential of our estimator through four applications. First, we develop a method for minimizing the maximum of N functions, improving on recent results and matching a lower bound up to logarithmic factors. Second and third, we recover state-of-the-art rates for projection-efficient and gradient-efficient optimization using simple algorithms with a transparent analysis. Finally, we show that an improved version of our estimator would yield a nearly linear-time, optimal-utility, differentially-private non-smooth stochastic optimization method.