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

Xiaochuan Gong, Jie Hao, Mingrui LiuSubmission to ICLR 2026 · Rejected

TL;DR

While Adam is the de facto optimizer for training modern deep architectures like Transformers and RNNs, existing theoretical convergence guarantees for Adam-type methods have been confined to single-level optimization. This paper bridges the gap by proposing AdamBO and VR-AdamBO, two Adam-style algorithms for stochastic bilevel optimization under realistic "unbounded smoothness" (non-Lipschitz gradient) conditions, achieving provable sample complexities of $\widetilde{\mathcal{O}}(\epsilon^{-4})$ and $\widetilde{\mathcal{O}}(\epsilon^{-3})$ alongside substantial empirical gains.

What Problem Does This Paper Address?

Bilevel optimization naturally formulates many machine learning workflows—such as meta-learning, hyperparameter tuning, and continual learning—where an outer (upper-level) objective depends on the solution of an inner (lower-level) problem.

Standard theoretical analyses of bilevel optimization usually rely on two assumptions:

  1. The objective functions have globally Lipschitz continuous gradients (bounded smoothness).
  2. The outer-level updates use SGD or normalized SGD.

However, modern architectures like Transformers and recurrent neural networks (RNNs) violate bounded smoothness: their gradient Lipschitz constants grow with the gradient norm itself. Furthermore, practitioners almost universally prefer Adam over SGD for attention-based models. Extending Adam to bilevel optimization under unbounded smoothness introduces severe challenges: upper-level hypergradient estimators suffer from non-negligible bias due to lower-level approximation errors, and the coordinate-wise, data-dependent step sizes of Adam complicate tracking error propagation between levels.

Methods

The authors introduce two novel algorithms tailored for stochastic bilevel optimization where the lower-level problem is strongly convex and the upper-level function is non-convex with generalized $(L_0, L_1)$-smoothness:

  • AdamBO: A single-loop algorithm that begins with a short SGD warm-start for the lower-level variable, then simultaneously executes SGD updates on the lower-level variable and standard coordinate-wise Adam updates on the upper-level variable. It estimates the implicit hypergradient using a stochastic Neumann series approximation.
  • VR-AdamBO: A variance-reduced variant combining STORM-style recursive momentum for upper-level Adam updates with periodic Stochastic Nesterov Accelerated Gradient (SNAG) updates and parameter averaging on the lower level.
  • Key Analytical Innovations:
  • Randomness Decoupling Lemma: Decouples the lower-level error tracking from the upper-level trajectory, bounding inner-variable drift with high probability using only the inner-level randomness.
  • Bilevel Stopping-Time Technique: Extends single-level stopped-process arguments to handle upper-level descent despite biased, stochastic hypergradient estimates and adaptive coordinate scaling.

Datasets

The authors evaluated their algorithms on two core tasks across RNN and Transformer backbones:

  • Sentiment140: Used for deep AUC maximization on imbalanced binary text classification, evaluated under imbalance ratios of $p = 0.8$ and $p = 0.9$ using 2-layer RNNs and 2-layer Transformers.
  • Stanford Natural Language Inference (SNLI): A corpus of 570k sentence pairs used for meta-learning / hyper-representation learning across $K = 500$ constructed few-shot tasks with a 3-layer recurrent network.
  • TREC: A question classification benchmark with 6 coarse-grained categories (tested in the appendix) evaluated with an 8-layer BERT backbone.

No new datasets were introduced.

Key Insights and Ideas

  • Decoupling Randomness is Key: Unlike normalized SGD (which enforces a predictable step size), Adam's step length varies across dimensions and iterations. The authors' randomness decoupling lemma proves that as long as the upper-level step sizes satisfy certain norm bounds, the lower-level error remains tightly controlled regardless of the specific upper-level path.
  • Matching Single-Level & SGD-based Bilevel Complexities:
  • AdamBO achieves an $\epsilon$-stationary point with $\widetilde{\mathcal{O}}(\epsilon^{-4})$ oracle complexity, matching non-adaptive bilevel methods (like SLIP) and single-level Adam under unbounded smoothness.
  • VR-AdamBO matches the optimal non-convex rate of $\widetilde{\mathcal{O}}(\epsilon^{-3})$, previously only achieved by variance-reduced SGD-type bilevel methods.
  • Larger Permissible Learning Rates: Compared to prior normalized SGD algorithms for unbounded smooth bilevel optimization (e.g., SLIP's $\eta = \widetilde{\Theta}(\epsilon^3)$ and AccBO's $\eta = \widetilde{\Theta}(\epsilon^2)$), AdamBO and VR-AdamBO admit substantially larger theoretical step sizes ($\widetilde{\Theta}(\epsilon^2)$ and $\widetilde{\Theta}(\epsilon)$, respectively).

Key Results

  • Deep AUC Maximization: On Sentiment140 with a Transformer model, AdamBO and VR-AdamBO outperformed all bilevel baselines (including StocBio, TTSA, SABA, SUSTAIN, BO-REP, SLIP, and AccBO), improving training AUC by at least 14% and testing AUC by at least 7%, while converging significantly faster in wall-clock time.
  • Meta-Learning: On SNLI and BERT-based question classification, AdamBO consistently outperformed gradient-based meta-learning methods (MAML, ANIL) as well as bilevel baselines in both training convergence rate and final test accuracy.
  • Hyperparameter Robustness: Empirical ablation confirmed that performance is robust across several orders of magnitude of the stability constant $\lambda$ (from $10^{-8}$ up to $10^{-3}$).

Limitations and Future Work

  • Strongly Convex Inner Objective: The theoretical guarantees assume the lower-level objective is strongly convex, leaving non-convex or weakly convex inner problems unaddressed.
  • Second-Order Oracle Calls: Both methods rely on stochastic Hessian-vector and Jacobian-vector products (via Neumann series approximation) for hypergradient estimation, which can be computationally intensive relative to purely first-order approximations.
  • Bounded Gradient Noise: Theoretical analysis assumes bounded or sub-Gaussian noise on stochastic gradients and Hessian approximations. Extending guarantees to heavy-tailed noise distributions represents an open avenue for future research.

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},
}

Loading related content...

Figure