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

Risheng Liu, Yaohua Liu, Shangzhi Zeng, Jin Zhang

TL;DR

This paper introduces the Augmented Iterative Trajectory (AIT) framework, which fixes two major flaws in gradient-based bilevel optimization: poor initialization and the "entire trajectory" trap. By making the starting point of the lower-level task learnable and dynamically truncating the optimization path, AIT achieves state-of-the-art results in complex tasks like Neural Architecture Search (NAS) and GAN training, even when the underlying problems are non-convex.

What Problem Does This Paper Address?

Bilevel Optimization (BLO) is a "leader-follower" game. Imagine an Upper-Level (UL) agent (the leader) trying to optimize a goal, but their success depends on a Lower-Level (LL) agent (the follower) solving their own sub-problem first. This structure is everywhere in modern AI:

  • Hyperparameter Optimization: The leader picks the learning rate; the follower trains the model.
  • Neural Architecture Search (NAS): The leader picks the network structure; the follower trains the weights.

Most current methods solve this by unrolling the follower's iterative optimization steps (the "trajectory") and calculating a "hyper-gradient" to update the leader. However, the authors identify two critical gaps:

  1. The Initialization Gap: Most methods start the follower's trajectory from a random or fixed point. If this start is poor, the leader gets noisy, slow-to-converge feedback.
  2. The Trajectory Trap: Standard methods use the entire optimization path to calculate gradients. In non-convex scenarios (common in deep learning), the follower's path can oscillate. Using the whole path—especially the final, potentially unstable iterate—leads to divergence or poor solutions.

Methods

The authors propose the Augmented Iterative Trajectory (AIT) framework, featuring two primary "augmentations":

  • Initialization Auxiliary (IA): Instead of picking a random starting point for the follower, AIT introduces an auxiliary variable ($z$) that represents the starting position. This $z$ is optimized alongside the leader's variables. Essentially, the system learns the best place to start the follower's training to reach the optimal solution faster.
  • Pessimistic Trajectory Truncation (PTT): To handle non-convex follower problems, AIT doesn't just look at the final step of the follower's training. Instead, it adopts a "pessimistic" view, identifying the worst-performing point along the trajectory and truncating the path there for gradient calculation. This stabilizes the feedback loop and prevents the leader from being misled by oscillatory behavior.

The framework also incorporates Nesterov’s acceleration and proximal prior regularization (using pre-trained weights as a "warm start" for the initialization variable) to further boost efficiency.

Datasets

The authors validated AIT across a wide range of benchmarks:

  • Toy Numerical Examples: Synthetic non-convex problems to prove theoretical convergence.
  • Data Hyper-Cleaning: MNIST, FashionMNIST, and CIFAR-10 (with corrupted labels).
  • Few-Shot Learning: MiniImageNet and TieredImageNet.
  • Neural Architecture Search (NAS): CIFAR-10.
  • Generative Adversarial Networks (GANs): A synthetic "2D Pentagram" distribution.

Key Insights and Ideas

  • Learnable Starts: The "aha moment" here is treating the initialization of an optimization path as a first-class citizen. By optimizing where the follower starts, you significantly reduce the number of steps needed to reach a high-quality response.
  • Stability through Pessimism: In non-convex landscapes, the "last iterate" is a dangerous metric. By focusing on the "worst case" along the path (PTT), the algorithm becomes robust against the oscillations that typically break gradient-based BLO.
  • Theoretical Breakthrough: The paper provides what the authors claim is the first convergence guarantee for BLO problems where the lower-level subproblem is non-convex—a major step forward for the mathematical grounding of NAS and Meta-Learning.

Key Results

  • Neural Architecture Search: On CIFAR-10, AIT found architectures that achieved 97.33% accuracy, outperforming the industry-standard DARTS (96.67%) and other competitors like CG and RHG, while using a more complex and expressive search space.
  • GAN Training: In the 2D Pentagram task (a classic test for "mode collapse"), AIT successfully captured all 10 modes of the distribution. Standard GAN variants (VGAN, UGAN) missed several modes, failing to represent the target shape accurately.
  • Data Cleaning: AIT consistently outperformed existing gradient-based methods (CG, Neumann, BDA) in test accuracy and F1 scores, especially when the follower's network was non-convex (multi-layer).

Limitations and Future Work

While AIT is powerful, the authors note a few areas for growth:

  • Computational Overhead: Optimizing the initialization variable $z$ adds some complexity, though the authors argue this is offset by the shorter trajectories enabled by PTT.
  • Stochastic Extensions: The current theory focuses on deterministic trajectories. Extending this to purely stochastic settings (using mini-batches for every step of the LL) is a logical next step.
  • High-Dimensional $z$: In extremely large models, the memory cost of storing and updating the initialization auxiliary could become a bottleneck, suggesting a need for more memory-efficient approximations.

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

Loading related content...

Figure