Adaptive Algorithms with Sharp Convergence Rates for Stochastic Hierarchical Optimization
Xiaochuan Gong, Jie Hao, Mingrui Liu
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{\sigma}}/T^{1/4})$ in $T$ iterations for the gradient norm, where $\bar{\sigma}$ is an upper bound on the stochastic gradient noise. Notably, these rates are obtained \emph{without requiring 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 and analysis rely on a novel synthesis of the momentum normalization technique for updating the upper-level variable with a carefully crafted adaptive stepsize scheme for both upper- and lower-level variables. Extensive experiments on synthetic and deep learning tasks demonstrate the effectiveness of our proposed algorithms