mlsanityData to 14 Oct 2026

Unified High-Probability Analysis of Stochastic Variance-Reduced Estimation

arXiv 2605.15388 ↗First posted 14 May 2026cs.LGcited by 1

Not on the map. Why?

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.

Key facts. Cited by 1 paper 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

23 of 145 references.

References · 23

  1. 2014Adam: A Method for Stochastic Optimizationcited by 37,240
  2. 2017Decoupled Weight Decay Regularizationcited by 1,831
  3. 2016An overview of gradient descent optimization algorithmscited by 1,033
  4. 2023Prodigy: An Expeditiously Adaptive Parameter-Free Learnercited by 133
  5. 2019The Complexity of Finding Stationary Points with Stochastic Gradient Descentcited by 35
  6. 2019Hybrid Stochastic Gradient Descent Algorithms for Stochastic Nonconvex Optimizationcited by 32
  7. 2023High-Probability Convergence for Composite and Distributed Stochastic Minimization and Variational Inequalities with Heavy-Tailed Noisecited by 24
  8. 2025Towards Weaker Variance Assumptions for Stochastic Optimizationcited by 17
  9. 2023Improved Convergence in High Probability of Clipped Gradient Methods with Heavy Tailscited by 13
  10. 2023Accelerated stochastic approximation with state-dependent noisecited by 11
  11. 2020An Optimal Hybrid Variance-Reduced Algorithm for Stochastic Composite Nonconvex Optimizationcited by 10
  12. 2025A single-loop SPIDER-type stochastic subgradient method for expectation-constrained nonconvex nonsmooth optimizationcited by 9
11 more
  1. 2026Lower Bounds and Proximally Anchored SGD for Non-Convex Minimization Under Unbounded Variancecited by 5
  2. 2020Stochastic Gradient Variance Reduction by Solving a Filtering Problemcited by 4
  3. 2019Mirror Descent for Constrained Optimization Problems with Large Subgradient Valuescited by 3
  4. 2025Structural Properties, Cycloid Trajectories and Non-Asymptotic Guarantees of EM Algorithm for Mixed Linear Regressioncited by 3
  5. 2026FedSGM: A Unified Framework for Constraint Aware, Bidirectionally Compressed, Multi-Step Federated Optimizationcited by 3
  6. 2024FedNMUT -- Federated Noisy Model Update Tracking Convergence Analysiscited by 2
  7. 2024Optimal Primal-Dual Algorithm with Last iterate Convergence Guarantees for Stochastic Convex Optimization Problemscited by 2
  8. 2022Solving Convex Smooth Function Constrained Optimization Is Almost As Easy As Unconstrained Optimizationcited by 1
  9. 2025Unified Theory of Adaptive Variance Reductioncited by 1
  10. 2026First-Order Softmax Weighted Switching Gradient Method for Distributed Stochastic Minimax Optimization with Stochastic Constraintscited by 1
  11. 2026RAMPAGE: RAndomized Mid-Point for debiAsed Gradient Extrapolationcited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026A Banach-Space Theory of Markovian Halpern Iteration for Non-Expansive Mapscited by 1