arXiv：cs.LG· Wei Jiang, Yibo Wang, Zechao Li·· 13 小时前
无需知道 Oracle 平滑常数的自适应方差缩减方法
Adaptive Variance Reduction without Knowing Oracle Smoothness
AI 导读
研究者提出一种两阶段方法，在未知平滑常数和方差界的情况下，让单一算法同时适配平均平滑、标准平滑与无噪声三种设定。给定梯度预算 T 时，其收敛率分别为 O(T^{-1/3})、O(T^{-1/4}) 和 O(T^{-1/2})；T 未知时另提出双路径方法，在随机设定下以对数因子达到对应速率。
正文
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.
| Subjects: | Optimization and Control (math.OC); Machine Learning (cs.LG) |
| Cite as: | arXiv:2610.13799 [math.OC] |
| (or arXiv:2610.13799v1 [math.OC] for this version) | |
| https://doi.org/10.48550/arXiv.2610.13799 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Yibo Wang [view email]
[v1]
Fri, 9 Oct 2026 16:13:42 UTC (16 KB)
来源：arXiv：cs.LG · arxiv.org