Search papers, labs, and topics across Lattice.
This paper introduces a novel two-phase adaptive variance reduction algorithm for stochastic non-convex optimization that dynamically switches between normalized momentum and variance reduction based on gradient differences, without prior knowledge of oracle smoothness or variance bounds. The algorithm achieves optimal convergence rates of $O(T^{-1/3})$ for average smoothness, $O(T^{-1/4})$ for standard smoothness, and $O(T^{-1/2})$ in the noiseless setting, and extends to unknown gradient budgets with logarithmic factors. This work bridges the gap between adaptive methods designed for specific smoothness conditions, offering a unified approach that performs optimally across different settings.
A single algorithm now achieves optimal convergence rates for stochastic non-convex optimization across average smoothness, standard smoothness, and noiseless settings, adapting dynamically without knowing any smoothness constants.
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.
