Adaptive Variance Reduction across Smoothness and Noise Conditions

원문 초록

In this paper, we study adaptive stochastic non-convex optimization under unknown smoothness and noise conditions. Our algorithms require no smoothness constant, noise bound, initial function gap, or oracle-regime label. We first propose a fixed-budget method that combines normalized momentum, recursive variance reduction, and a fresh gradient stage, followed by fresh validation of the candidates. We prove that the same output has expected gradient norm $O(T^{-1/4})$ under objective smoothness and bounded noise variance, $O(T^{-1/3})$ under average smoothness, and $O(T^{-1/2})$ for noiseless gradients, where $T$ counts individual gradient evaluations. We then develop an anytime algorithm whose three optimization paths preserve their endpoints across reporting and budget-extension boundaries. The same three rates hold at every deterministic query budget, although the algorithm receives no information about the budget $T$. The analysis combines a scale potential, a uniform second-moment bound, and accounting for candidates retained through unfinished blocks. An optional sample-mean selector further reduces cumulative validation work from $O(T)$ to $O(T^{2/3})$ while preserving these rates.