Augmenting Iterative Trajectory for Bilevel Optimization: Methodology, Analysis and Extensions

Risheng Liu, Yaohua Liu, Shangzhi Zeng, Jin Zhang

Abstract

In recent years, there has been a surge of machine learning applications developed with hierarchical structure, which can be approached from a Bi-Level Optimization (BLO) perspective. However, most existing gradient-based methods overlook the interdependence between hyper-gradient calculation and Lower-Level (LL) iterative trajectory, focusing solely on the former. Consequently, convergence theory is constructed with restrictive LL assumptions, which are often challenging to satisfy in real-world scenarios. In this work, we thoroughly analyze the constructed iterative trajectory and highlight two deficiencies: empirically chosen initialization and default use of the entire trajectory for hyper-gradient calculation. To address these issues, we introduce two augmentation techniques—Initialization Auxiliary (IA) and Pessimistic Trajectory Truncation (PTT)—and investigate various extension strategies to construct Augmented Iterative Trajectory (AIT) for corresponding BLO scenarios. Theoretically, we provide convergence analysis for AIT under different LL assumptions, including non-convex LL subproblems.

Introduction

Bilevel Optimization (BLO) is fundamentally a "leader-follower" game. An Upper-Level (UL) agent (the leader) seeks to optimize a primary objective, but their success is contingent upon a Lower-Level (LL) agent (the follower) solving a nested sub-problem. This structure is prevalent in modern AI, from Hyperparameter Optimization to Neural Architecture Search (NAS).

Standard gradient-based methods typically solve BLO by unrolling the follower's iterative optimization steps—the "trajectory"—to calculate a hyper-gradient for the leader. However, this approach suffers from two critical gaps:

  1. The Initialization Gap: Followers usually start from a fixed or random point. Poor initialization leads to noisy feedback and slow convergence.
  2. The Trajectory Trap: Using the entire optimization path for gradients is risky in non-convex landscapes common in deep learning, where trajectories can oscillate or diverge.

Methodology: The AIT Framework

The proposed Augmented Iterative Trajectory (AIT) framework addresses these gaps through two primary innovations:

Initialization Auxiliary (IA)

Instead of a static starting point, AIT introduces an auxiliary variable ($z$) representing the follower's initialization. This variable is optimized alongside the leader’s variables, effectively learning the optimal starting position to reach a high-quality response faster.

Pessimistic Trajectory Truncation (PTT)

To handle non-convexity, AIT adopts a "pessimistic" view. Rather than relying on the final iterate, it identifies the worst-performing point along the trajectory and truncates the path there for gradient calculation. This stabilizes the feedback loop against oscillations.

The Proposed AIT_NC Algorithm for non-convex lower-level subproblems.

Theoretical and Comparative Analysis

AIT provides a robust theoretical foundation, offering convergence guarantees even when the lower-level subproblem is non-convex—a significant advancement over traditional methods that require strong convexity.

Comparison of AIT with existing gradient-based BLO methods regarding assumptions like Lower-Level Strong convexity (LLS) and Convexity (LLC).

As illustrated in the comparison table, AIT is the only method that consistently operates without requiring Lower-Level Strong convexity (LLS) or Lower-Level Convexity (LLC) while supporting acceleration (A.).

Experimental Results

The effectiveness of AIT was validated across several challenging domains:

  • Neural Architecture Search (NAS): On CIFAR-10, AIT achieved 97.33% accuracy, outperforming DARTS (96.67%) and other gradient-based competitors like CG and RHG.
  • Generative Adversarial Networks (GANs): In the 2D Pentagram task, AIT successfully captured all 10 modes of the distribution, whereas standard variants like VGAN and UGAN suffered from mode collapse.
  • Data Hyper-Cleaning: AIT consistently outperformed existing methods (CG, Neumann, BDA) in test accuracy and F1 scores, particularly when utilizing non-convex multi-layer follower networks.

Conclusion

The AIT framework represents a paradigm shift in BLO by treating the iterative trajectory as an augmentable component rather than a fixed path. By making initialization learnable and employing pessimistic truncation, AIT provides both theoretical stability and state-of-the-art performance in complex, non-convex machine learning tasks. Future work will explore extending these deterministic trajectories into purely stochastic settings.

Summary updated

Abstract

In recent years, there has been a surge of machine learning applications developed with hierarchical structure, which can be approached from Bi-Level Optimization (BLO) perspective. However, most existing gradient-based methods overlook the interdependence between hyper-gradient calculation and Lower-Level (LL) iterative trajectory, focusing solely on the former. Consequently, convergence theory is constructed with restrictive LL assumptions, which are often challenging to satisfy in real-world scenarios. In this work, we thoroughly analyze the constructed iterative trajectory, and highlight two deficiencies, including empirically chosen initialization and default use of entire trajectory for hyper-gradient calculation. To address these issues, we introduce two augmentation techniques including Initialization Auxiliary (IA) and Pessimistic Trajectory Truncation (PTT), and investigate various extension strategies such as prior regularization, different iterative mapping schemes and acceleration dynamics to construct Augmented Iterative Trajectory (AIT) for corresponding BLO scenarios (e.g., LL convexity and LL non-convexity). Theoretically, we provide convergence analysis for AIT and its variations under different LL assumptions, and establish the convergence analysis for BLOs with non-convex LL subproblem. Finally, we demonstrate the effectiveness of AIT through three numerical examples, typical learning and vision applications (e.g., data hyper-cleaning and few-shot learning) and more challenging tasks such as neural architecture search.
BibTeX
@article{liu2025augmenting,
  author = {Risheng Liu and Yaohua Liu and Shangzhi Zeng and Jin Zhang},
  title = {{Augmenting Iterative Trajectory for Bilevel Optimization: Methodology, Analysis and Extensions}},
  journal = {IEEE Transactions on Pattern Analysis and Machine Intelligence},
  year = {2025},
  doi = {10.1109/tpami.2025.3644443},
}
Figure