Unified High-Probability Analysis of Stochastic Variance-Reduced Estimation
Summary
This paper presents a unified theoretical framework for stochastic variance-reduced estimation, deriving high-probability bounds via a new Freedman inequality and improving oracle complexities for constrained optimization.
View Cached Full Text
Cached at: 05/18/26, 06:40 AM
# Unified High-Probability Analysis of Stochastic Variance-Reduced Estimation
Source: [https://arxiv.org/abs/2605.15388](https://arxiv.org/abs/2605.15388)
[View PDF](https://arxiv.org/pdf/2605.15388)
> 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\.
## Submission history
From: Zhankun Luo \[[view email](https://arxiv.org/show-email/e90fa7e4/2605.15388)\] **\[v1\]**Thu, 14 May 2026 20:17:10 UTC \(169 KB\)Similar Articles
Beyond Bounded Variance: Variance-Reduced Normalized Methods for Nonconvex Optimization under Blum-Gladyshev Noise
This paper studies nonconvex stochastic optimization under Blum-Gladyshev noise, where gradient variance grows with distance from initialization. It proves convergence guarantees for normalized SGD with momentum and a variance-reduced STORM method, achieving minimax optimal rates under certain conditions.
Zeroth-Order Non-Log-Concave Sampling with Variance Reduction and Applications to Inverse Problems
Proposes a variance-reduced zeroth-order Langevin sampling method for non-log-concave distributions, establishing the first non-asymptotic convergence guarantees, and applies it to inverse problems with score-based generative priors.
Variance Reduction for Heavy-Tailed Monetization Metrics in Ranking Experiments via Post-Stratification
Researchers present a practical variance reduction framework combining post-stratification with CUPED for heavy-tailed monetization metrics in ranking experiments, deployed at ShareChat to achieve equivalent statistical confidence with 45% less traffic. The paper is accepted at SIGIR 2026.
Heuristic Pathologies and Further Variance Reduction via Uncertainty Propagation in the AIVAT Family of Techniques
This paper identifies vulnerabilities in the AIVAT variance reduction technique when the heuristic value function is not fixed prior to evaluation, and shows how to propagate heuristic uncertainty to further reduce variance, achieving a 43% reduction in the number of samples needed for statistical conclusions.
High-Probability PL-SGD with Markovian Noise: Optimal Mixing and Tail Dependence
This paper provides optimal high-probability bounds for stochastic gradient descent under Markovian noise for PL-smooth objectives, closing gaps between expectation and high-probability guarantees and extending to heavy-tailed settings with matching lower bounds.