On the Convergence of Adam-Type Algorithm for Bilevel Optimization under Unbounded Smoothness

Xiaochuan Gong, Jie Hao, Mingrui Liu

Abstract

Adam has become one of the most popular optimizers for training modern deep neural networks, such as transformers. However, its applicability is largely restricted to single-level optimization problems. In this paper, we aim to extend vanilla Adam to tackle bilevel optimization problems, which have important applications in machine learning, such as meta-learning. In particular, we study stochastic bilevel optimization problems where the lower-level function is strongly convex and the upper-level objective is nonconvex with potentially unbounded smoothness. This unbounded smooth objective function covers a broad class of neural networks, including transformers, which may exhibit non-Lipschitz gradients. In this work, we introduce AdamBO, a single-loop Adam-type method that achieves $\widetilde{O}(\epsilon^{-4})$ oracle complexity to find $\epsilon$-stationary points, where the oracle calls involve stochastic gradient or Hessian/Jacobian-vector product evaluations. The key to our analysis is a novel randomness decoupling lemma that provides refined control over the lower-level variable. We conduct extensive experiments on various machine learning tasks involving bilevel formulations with recurrent neural networks (RNNs) and transformers, demonstrating the effectiveness of our proposed Adam-type algorithm.

Introduction

Bilevel optimization involves an upper-level objective that depends on the solution of a lower-level objective. This structure is fundamental to meta-learning, hyperparameter optimization, and reinforcement learning. While the Adam optimizer is the gold standard for training modern deep networks like Transformers, its use in bilevel optimization has been poorly understood theoretically. Most existing bilevel theories assume "Lipschitz smoothness," where gradients do not change abruptly. However, modern architectures like RNNs and Transformers often exhibit unbounded smoothness, where gradients can fluctuate wildly.

This work addresses two primary challenges: adapting Adam’s coordinate-wise learning rates to the nested structure of bilevel problems and guaranteeing convergence when the loss landscape is "unbounded" and non-smooth.

Methods: The AdamBO Algorithm

We propose AdamBO (Adam for Bilevel Optimization), a single-loop algorithm that updates both levels simultaneously. Unlike "double-loop" methods that solve the lower-level problem to completion at every step, AdamBO maintains efficiency by updating the lower level with SGD and the upper level with vanilla Adam.

Key Components

  • Simultaneous Updates: The algorithm uses a few "warm-start" SGD steps for the lower-level variable, followed by concurrent updates for both levels.
  • Hypergradient Estimation: A Neumann series approach is employed to estimate the hypergradient (the gradient of the upper-level objective with respect to the upper-level parameters).
  • Randomness Decoupling Lemma: This is the core theoretical innovation. Proving convergence for Adam is difficult because the update at step $t$ depends on the entire history of gradients, creating complex dependencies. The proposed lemma "decouples" the randomness of the lower-level SGD from the adaptive updates of the upper-level Adam, ensuring the lower-level error remains controlled.

Experiments and Results

The researchers evaluated AdamBO on several challenging machine learning tasks, including BERT-based meta-learning (TREC dataset), RNN-based meta-learning (SNLI dataset), and Deep AUC Maximization on imbalanced text classification (Sentiment140).

Performance and Efficiency

AdamBO demonstrated superior performance across all tasks. In BERT-based meta-learning, it converged faster and reached higher accuracy than major baselines such as MAML, ANIL, and StocBio. On imbalanced text classification with Transformers, AdamBO improved training AUC by at least 14% and testing AUC by 7% compared to other bilevel algorithms.

Performance comparison of AdamBO against baseline methods in terms of accuracy over epochs and running time.

As shown in Figure 1, AdamBO reaches high-quality solutions in significantly less wall-clock time than non-adaptive or double-loop alternatives. The adaptive learning rates of AdamBO prove as effective for the meta-level of bilevel problems as they are for single-level training.

Conclusion

AdamBO bridges the gap between practice and theory by providing an $O(\epsilon^{-4})$ oracle complexity guarantee under realistic "unbounded smoothness" conditions. While the current proof requires the lower-level objective to be strongly convex, the success of AdamBO in meta-learning setups involving "adapter" layers highlights its practical utility. Future work will focus on improving theoretical bounds regarding the $\lambda$ constant and extending the theory to non-convex lower-level problems.

Summary updated

Abstract

Adam has become one of the most popular optimizers for training modern deep neural networks, such as transformers. However, its applicability is largely restricted to single-level optimization problems. In this paper, we aim to extend vanilla Adam to tackle bilevel optimization problems, which have important applications in machine learning, such as meta-learning. In particular, we study stochastic bilevel optimization problems where the lower-level function is strongly convex and the upper-level objective is nonconvex with potentially unbounded smoothness. This unbounded smooth objective function covers a broad class of neural networks, including transformers, which may exhibit non-Lipschitz gradients. In this work, we introduce AdamBO, a single-loop Adam-type method that achieves $\widetilde{O}(\epsilon^{-4})$ oracle complexity to find $\epsilon$-stationary points, where the oracle calls involve stochastic gradient or Hessian/Jacobian-vector product evaluations. The key to our analysis is a novel randomness decoupling lemma that provides refined control over the lower-level variable. We conduct extensive experiments on various machine learning tasks involving bilevel formulations with recurrent neural networks (RNNs) and transformers, demonstrating the effectiveness of our proposed Adam-type algorithm.
BibTeX
@misc{gong2025convergence,
  author = {Xiaochuan Gong and Jie Hao and Mingrui Liu},
  title = {{On the Convergence of Adam-Type Algorithm for Bilevel Optimization under Unbounded Smoothness}},
  year = {2025},
  eprint = {2503.03908},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2503.03908},
}
Figure