提出自适应算法,实现随机分层优化的最优收敛速度。
Adaptive Algorithms with Sharp Convergence Rates for Stochastic Hierarchical Optimization
- 结合动量归一化与自适应参数选择,设计新算法。
- 在T次迭代下,梯度范数收敛至$ ilde{O}(1/ oot{}{T} + oot{}{arσ}/T^{1/4})$。
- 无需噪声水平先验,适用于高低噪声场景,适合深度学习应用。
分层优化涉及相互依赖的决策变量和目标,如极小极大和双层问题。现有方法在随机优化设置中缺乏自适应性:无法在不预先知晓噪声大小的情况下,对广泛的梯度噪声水平实现最优收敛速率。本文针对两类重要随机分层优化问题——非凸-强凹极小极大优化和非凸-强凸双层优化,提出新型自适应算法。其在T次迭代下的梯度范数收敛速率达$ ilde{O}(1/ oot{}{T} + oot{}{arσ}/T^{1/4})$,其中$arσ$为随机梯度噪声的上界。关键在于无需噪声水平先验,可在低噪与高噪环境下自动适应。据我们所知,这是首个针对随机分层优化的自适应且精确的收敛保证。算法设计融合动量归一化与新颖的自适应参数选择。在合成数据和深度学习任务上的大量实验验证了算法有效性。
原文摘要 · Abstract (English)
Hierarchical optimization refers to problems with interdependent decision variables and objectives, such as minimax and bilevel formulations. While various algorithms have been proposed, existing methods and analyses lack adaptivity in stochastic optimization settings: they cannot achieve optimal convergence rates across a wide spectrum of gradient noise levels without prior knowledge of the noise magnitude. In this paper, we propose novel adaptive algorithms for two important classes of stochastic hierarchical optimization problems: nonconvex-strongly-concave minimax optimization and nonconvex-strongly-convex bilevel optimization. Our algorithms achieve sharp convergence rates of $\widetilde{O}(1/\sqrt{T} + \sqrt{\barσ}/T^{1/4})$ in $T$ iterations for the gradient norm, where $\barσ$ is an upper bound on the stochastic gradient noise. Notably, these rates are obtained without prior knowledge of the noise level, thereby enabling automatic adaptivity in both low and high-noise regimes. To our knowledge, this work provides the first adaptive and sharp convergence guarantees for stochastic hierarchical optimization. Our algorithm design combines the momentum normalization technique with novel adaptive parameter choices. Extensive experiments on synthetic and deep learning tasks demonstrate the effectiveness of our proposed algorithms.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。