An Accelerated Algorithm for Stochastic Bilevel Optimization under Unbounded Smoothness
This paper investigates a class of stochastic bilevel optimization problems where the upper-level function is nonconvex with potentially unbounded smoothness and the lower-level problem is strongly convex. These problems have significant applications in sequential data learning, such as text classification using recurrent neural networks. The unbounded smoothness is characterized by the smoothness constant of the upper-level function scaling linearly with the gradient norm, lacking a uniform upper bound. Existing state-of-the-art algorithms require $\widetilde{O}(1/\epsilon^4)$ oracle calls of stochastic gradient or Hessian/Jacobian-vector product to find an $\epsilon$-stationary point. However, it remains unclear if we can further improve the convergence rate when the assumptions for the function in the population level also hold for each random realization almost surely. To address this issue, we propose a new Accelerated Bilevel Optimization algorithm named AccBO. The algorithm updates the upper-level variable by normalized stochastic gradient descent with recursive momentum and the lower-level variable by the stochastic Nesterov accelerated gradient descent algorithm with averaging. We prove that our algorithm achieves an oracle complexity of $\widetilde{O}(1/\epsilon^3)$ to find an $\epsilon$-stationary point, when the lower-level stochastic gradient's variance is $O(\epsilon)$. Our proof relies on a novel lemma characterizing the dynamics of stochastic Nesterov accelerated gradient descent algorithm under distribution drift with high probability for the lower-level variable, which is of independent interest and also plays a crucial role in analyzing the hypergradient estimation error over time. Experimental results on various tasks confirm that our proposed algorithm achieves the predicted theoretical acceleration and significantly outperforms baselines in bilevel optimization.
Code (1)
Tasks
Bilevel OptimizationLEMMAtext-classificationText ClassificationMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Enhanced Bilevel Optimization via Bregman Distance
Bilevel optimization has been recently used in many machine learning problems such as hyperparameter optimization, policy optimization, and meta learning. Although many bilevel optimization methods have been proposed, th…
Bilevel OptimizationHyperparameter OptimizationMeta-LearningRepresentation LearningBiAdam: Fast Adaptive Bilevel Optimization Methods
Bilevel optimization recently has attracted increased interest in machine learning due to its many applications such as hyper-parameter optimization and meta learning. Although many bilevel methods recently have been pro…
Bilevel OptimizationMeta-LearningRepresentation LearningNonconvex Decentralized Stochastic Bilevel Optimization under Heavy-Tailed Noise
Existing decentralized stochastic optimization methods assume the lower-level loss function is strongly convex and the stochastic gradient noise has finite variance. These strong assumptions typically are not satisfied i…
Stochastic OptimizationBilevel OptimizationContextual Bilevel Reinforcement Learning for Incentive Alignment
The optimal policy in various real-world strategic decision-making problems depends both on the environmental configuration and exogenous events. For these settings, we introduce Contextual Bilevel Reinforcement Learning…
Bilevel OptimizationDecision Makingreinforcement-learningReinforcement LearningLower Bounds and Accelerated Algorithms for Bilevel Optimization
Bilevel optimization has recently attracted growing interests due to its wide applications in modern machine learning problems. Although recent studies have characterized the convergence rate for several such popular alg…
Bilevel Optimization