# Adaptive Variance Reduction without Knowing Oracle Smoothness

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 3 of its 3 references that are in the map.
- First posted on arXiv 9 Oct 2026.

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

- [Momentum-Based Variance Reduction in Non-Convex SGD](https://mlsanity.com/paper/1905.10018/) (2019)
- [Convergence of AdaGrad for Non-convex Objectives: Simple Proofs and Relaxed Assumptions](https://mlsanity.com/paper/2305.18471/) (2023)
- [Adaptive Variance Reduction for Stochastic Optimization under Weaker Assumptions](https://mlsanity.com/paper/2406.01959/) (2024)

## Abstract (arXiv)

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.