Unified High-Probability Analysis of Stochastic Variance-Reduced Estimation

Zhankun Luo, Antesh Upadhyay, M. Berk Sahin, Sang Bin Moon, Anuran Makur, Abolfazl HashemiarXiv 2026 · arXiv

TL;DR

This paper introduces a unified mathematical framework that brings together popular stochastic estimators like momentum, STORM, and PAGE under a single recursive template. By developing a new dimension-free "Freedman inequality" for vector martingales, the authors provide robust high-probability guarantees for these methods in both Euclidean and non-Euclidean spaces, ultimately improving the sample complexity of constrained optimization from $\tilde{\mathcal{O}}(\varepsilon^{-4})$ to $\tilde{\mathcal{O}}(\varepsilon^{-3})$.

What Problem Does This Paper Address?

In large-scale machine learning, we rarely have access to the "true" gradient of a function. Instead, we use stochastic oracles—noisy samples that estimate the direction we should move. To make these algorithms reliable, researchers use "variance reduction" techniques (like STORM or SPIDER) to filter out noise.

However, the field has faced three major hurdles:

  1. Fragmented Theory: Every new estimator usually requires a bespoke, complex proof. There hasn't been a "grand unified theory" explaining why they all work.
  2. The "Average" Trap: Most existing proofs only guarantee performance on average (in expectation). This hides rare but significant failures that can be disastrous in safety-critical applications or constrained optimization.
  3. Euclidean Bias: Most high-probability proofs only work in standard flat (Euclidean) spaces, failing to account for more complex geometries like the probability simplex, where "Mirror Descent" is the preferred tool.

Methods

The authors propose a Unified Estimator defined by a simple recursion. This estimator uses three "knobs" that can be tuned to recover almost any classical method:

  • Memory Retention ($\beta_t$): How much of the previous estimate we keep.
  • Reset Probability ($p_t$): How often we throw everything away and start fresh with a large batch of samples.
  • Correction Term ($T_t$): How we adjust the old estimate to account for the fact that the algorithm has moved to a new position.
The unified framework recovers classical estimators and suggests new second-order variants.

To analyze this framework, the authors developed a new vector-valued Freedman inequality. In probability theory, Freedman's inequality is a powerful tool for bounding the "tails" of a process (the probability of extreme errors). The authors' version is "dimension-free," meaning the guarantees don't get significantly worse as the number of parameters in your model grows, and it works in smooth Banach spaces (a broad category of mathematical spaces that includes non-Euclidean geometries).

Datasets

Not discussed in the paper. This is a theoretical work focused on proving mathematical convergence rates and oracle complexities rather than empirical benchmarking on specific datasets.

Key Insights and Ideas

  • The Correction Term is Key: The authors show that the main difference between "momentum" and "variance reduction" is simply how you correct for iterate movement. Momentum uses a "zeroth-order" correction (none), while methods like STORM use a "first-order" correction to align past information with the current position.
  • High-Probability is the New Standard: By moving away from "expected" results, the authors provide a "tail-envelope." This gives engineers a "confidence level" (e.g., "this algorithm will succeed with 99.9% certainty"), which is essential for constrained problems where violating a constraint even once is unacceptable.
  • Tracking Constraints: A clever insight in the paper is applying these gradient-style estimators to track constraint values. In constrained optimization, knowing if you are "feasible" (within bounds) is just as hard as finding the gradient. The authors show that variance reduction helps here just as much as it does for the objective function.

Key Results

The paper's most significant impact is on Expectation-Constrained Stochastic Optimization.

  • Complexity Leap: For problems where you must minimize a function while satisfying a noisy constraint, they improved the "Oracle Complexity" (the number of samples needed to reach a solution) from $\tilde{\mathcal{O}}(\varepsilon^{-4})$ to $\tilde{\mathcal{O}}(\varepsilon^{-3})$. This is a massive improvement in efficiency for high-precision requirements.
  • Mirror Descent Support: They established the first high-probability stationarity guarantees for variance-reduced mirror descent in non-Euclidean spaces, showing a logarithmic dependence on the confidence level ($1/\delta$).
Dominant complexity rates for unconstrained (Application 1) and constrained (Application 2) optimization.

Limitations and Future Work

While the paper is a major theoretical step forward, the authors note a few areas for growth:

  • Noise Assumptions: The current proofs assume "sub-Gaussian" noise (noise that decays very quickly). Real-world data often has "heavy tails," and extending this unified framework to more relaxed noise models (like the BG-0 regime) remains an open challenge.
  • Step-Size Tuning: The analysis currently relies on constant step sizes. Developing "adaptive" versions that automatically tune themselves during the run—while maintaining these high-probability guarantees—is a logical next step.
  • Distributed Settings: The authors suggest that this "correction-term" perspective could be very useful in decentralized or federated learning, where "client drift" is a major source of error.

Summary updated

Abstract

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 $\tilde{\mathcal{O}}(\varepsilon^{-3})$ oracle-complexity bounds for stochastic optimization with expectation constraints, improving upon the existing $\tilde{\mathcal{O}}(\varepsilon^{-4})$ complexity by leveraging variance-reduced estimation for the first time in this setting.
BibTeX
@misc{luo2026unified,
  author = {Zhankun Luo and Antesh Upadhyay and M. Berk Sahin and Sang Bin Moon and Anuran Makur and Abolfazl Hashemi},
  title = {{Unified High-Probability Analysis of Stochastic Variance-Reduced Estimation}},
  year = {2026},
  eprint = {2605.15388},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2605.15388},
}
Figure