# Unified High-Probability Analysis of Stochastic Variance-Reduced Estimation

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 145 references that are in the map.
- First posted on arXiv 14 May 2026.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Decoupled Weight Decay Regularization](https://mlsanity.com/paper/1711.05101/) (2017)
- [An overview of gradient descent optimization algorithms](https://mlsanity.com/paper/1609.04747/) (2016)
- [Prodigy: An Expeditiously Adaptive Parameter-Free Learner](https://mlsanity.com/paper/2306.06101/) (2023)
- [The Complexity of Finding Stationary Points with Stochastic Gradient Descent](https://mlsanity.com/paper/1910.01845/) (2019)
- [Hybrid Stochastic Gradient Descent Algorithms for Stochastic Nonconvex Optimization](https://mlsanity.com/paper/1905.05920/) (2019)
- [High-Probability Convergence for Composite and Distributed Stochastic Minimization and Variational Inequalities with Heavy-Tailed Noise](https://mlsanity.com/paper/2310.01860/) (2023)
- [Towards Weaker Variance Assumptions for Stochastic Optimization](https://mlsanity.com/paper/2504.09951/) (2025)
- [Improved Convergence in High Probability of Clipped Gradient Methods with Heavy Tails](https://mlsanity.com/paper/2304.01119/) (2023)
- [Accelerated stochastic approximation with state-dependent noise](https://mlsanity.com/paper/2307.01497/) (2023)
- [An Optimal Hybrid Variance-Reduced Algorithm for Stochastic Composite Nonconvex Optimization](https://mlsanity.com/paper/2008.09055/) (2020)
- [A single-loop SPIDER-type stochastic subgradient method for expectation-constrained nonconvex nonsmooth optimization](https://mlsanity.com/paper/2501.19214/) (2025)
- [Lower Bounds and Proximally Anchored SGD for Non-Convex Minimization Under Unbounded Variance](https://mlsanity.com/paper/2604.16620/) (2026)
- [Stochastic Gradient Variance Reduction by Solving a Filtering Problem](https://mlsanity.com/paper/2012.12418/) (2020)
- [Mirror Descent for Constrained Optimization Problems with Large Subgradient Values](https://mlsanity.com/paper/1908.00218/) (2019)
- [Structural Properties, Cycloid Trajectories and Non-Asymptotic Guarantees of EM Algorithm for Mixed Linear Regression](https://mlsanity.com/paper/2511.04937/) (2025)
- [FedSGM: A Unified Framework for Constraint Aware, Bidirectionally Compressed, Multi-Step Federated Optimization](https://mlsanity.com/paper/2601.16897/) (2026)
- [FedNMUT -- Federated Noisy Model Update Tracking Convergence Analysis](https://mlsanity.com/paper/2403.13247/) (2024)
- [Optimal Primal-Dual Algorithm with Last iterate Convergence Guarantees for Stochastic Convex Optimization Problems](https://mlsanity.com/paper/2410.18513/) (2024)
- [Solving Convex Smooth Function Constrained Optimization Is Almost As Easy As Unconstrained Optimization](https://mlsanity.com/paper/2210.05807/) (2022)
- [Unified Theory of Adaptive Variance Reduction](https://mlsanity.com/paper/2511.04569/) (2025)
- [First-Order Softmax Weighted Switching Gradient Method for Distributed Stochastic Minimax Optimization with Stochastic Constraints](https://mlsanity.com/paper/2603.05774/) (2026)
- [RAMPAGE: RAndomized Mid-Point for debiAsed Gradient Extrapolation](https://mlsanity.com/paper/2603.22155/) (2026)

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

- [A Banach-Space Theory of Markovian Halpern Iteration for Non-Expansive Maps](https://mlsanity.com/paper/2608.15966/) (2026)

## Abstract (arXiv)

Stochastic estimators are fundamental to large-scale optimization, where population quantities must be inferred from noisy oracle observations. Although influential methods such as momentum, SPIDER, STORM, and PAGE have been highly successful, their analyses are largely estimator-specific and expectation-based, obscuring the structural tradeoffs that determine reliability. In this paper, we develop a unified framework for stochastic variance-reduced estimation based on a recursion with three components: memory retention, reset probability, and a correction term for iterate movement. This framework recovers several classical estimators, motivates new second-order variants, and yields a bias-variance decomposition of estimation error. Our main result is a unified high-probability bound proved using a new dimension-free vector-valued Freedman inequality, valid for smooth normed spaces involving random sums of vector martingales. The result applies in both Euclidean and non-Euclidean settings, including the analysis of mirror-descent-based methods in Banach spaces. As applications, we obtain high-probability oracle complexities for unconstrained optimization with mirror descent, establishing the logarithmic dependence on the confidence level. We also derive the first tildeO(varepsilon-3) oracle-complexity bounds for stochastic optimization with expectation constraints, improving upon the existing tildeO(varepsilon-4) complexity by leveraging variance-reduced estimation for the first time in this setting.