Adaptive Variance Reduction without Knowing Oracle Smoothness
Abstract
Variance reduction improves the convergence rate of stochastic non-convex optimization under the average smoothness condition. Existing adaptive variance reduction methods are especially designed for average smoothness and do not adapt to standard smoothness. In this paper, we study how one algorithm can adapt to these two settings and the noiseless setting without knowing the smoothness constants or the variance bound. Given the gradient budget T, we develop a two-phase method. The first phase compares two independent gradients and switches to normalized momentum when their difference exceeds a threshold. This phase provides both a candidate with standard smooth and noiseless guarantees and also ensures a bounded expected function gap for the second variance reduction phase. The resulting rates are O(T−1/3) under average smoothness, O(T−1/4) under standard smoothness, and O(T−1/2) without noise. When T is unknown, we propose a method with two paths that attain the corresponding rates with logarithmic factors in the stochastic settings. Here, we use a variance reduction path to deal with average smoothness and employ the AdaGrad-Norm for standard smoothness and noiseless setting. Neither method restarts from the initial point or requires a growing number of oracle calls in each round.
Related
- Interior smoothness and zero-variance geometry for finite-maturity Heston American puts
- Variance Reduction Note 3: The Convergence of PAGE
- Variance Reduction Note 2: The Convergence of SPIDER
- Variance Reduction Note 4: The Convergence of SVRG
- LQG solution for POMDP without estimating states: A minimum variance approach
BibTeX
@misc{jiang2026adaptive,
title = {{Adaptive Variance Reduction without Knowing Oracle Smoothness}},
author = {Wei Jiang and Yibo Wang and Zechao Li},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.13799},
eprint = {2610.13799},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.13799},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Adaptive Variance Reduction without Knowing Oracle Smoothness
AU - Wei Jiang
AU - Yibo Wang
AU - Zechao Li
PY - 2026
DA - 2026/10/09
PB - arXiv
DO - 10.48550/arxiv.2610.13799
UR - https://arxiv.org/abs/2610.13799
AB - Variance reduction improves the convergence rate of stochastic non-convex optimization under the average smoothness condition. Existing adaptive variance reduction methods are especially designed for average smoothness and do not adapt to standard smoothness. In this paper, we study how one algorithm can adapt to these two settings and the noiseless setting without knowing the smoothness constants or the variance bound. Given the gradient budget T, we develop a two-phase method. The first phase compares two independent gradients and switches to normalized momentum when their difference exceeds a threshold. This phase provides both a candidate with standard smooth and noiseless guarantees and also ensures a bounded expected function gap for the second variance reduction phase. The resulting rates are O(T^−1/3) under average smoothness, O(T^−1/4) under standard smoothness, and O(T^−1/2) without noise. When T is unknown, we propose a method with two paths that attain the corresponding rates with logarithmic factors in the stochastic settings. Here, we use a variance reduction path to deal with average smoothness and employ the AdaGrad-Norm for standard smoothness and noiseless setting. Neither method restarts from the initial point or requires a growing number of oracle calls in each round.
ER -