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:
- The objective functions have globally Lipschitz continuous gradients (bounded smoothness).
- 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