Alternating Gradient-Type Algorithm for Bilevel Optimization with Inexact Lower-Level Solutions via Moreau Envelope–Based Reformulation

Xiaoning Bai, Shangzhi Zeng, Adam Zhang, L. ZhangSIAM 2026 · DOI · arXiv

TL;DR

The authors introduce AGILS, an alternating gradient-type algorithm designed to solve complex bilevel optimization problems without requiring exact solutions for the lower-level task at every step. By leveraging a Moreau envelope-based reformulation and a smart feasibility correction mechanism, AGILS achieves state-of-the-art computational efficiency and accuracy in hyperparameter tuning tasks.

What Problem Does This Paper Address?

Bilevel optimization is essentially "optimization within optimization"—think of a leader-follower game where the leader (upper-level) chooses a strategy, and the follower (lower-level) responds optimally. This structure is perfect for machine learning hyperparameter tuning, where the upper level minimizes validation error and the lower level trains the model.

However, two major roadblocks exist:

  1. Computational Cost: Most algorithms require solving the lower-level problem perfectly at every single iteration, which is incredibly slow.
  2. Mathematical Instability: If the lower-level problem doesn't have a unique, "strongly convex" solution (common in models like Lasso), the gradient of the leader's objective (the "hypergradient") becomes difficult to define or compute accurately.

This paper tackles these issues by proposing a method that works with inexact lower-level solutions while remaining mathematically rigorous.

Methods

The core of the paper is the AGILS (Alternating Gradient-type algorithm with Inexact Lower-level Solutions) algorithm. Its novelty lies in three main components:

  • Moreau Envelope Reformulation: Instead of using a standard "value function" constraint (which is often non-smooth and difficult to handle), the authors use a relaxed version based on the Moreau envelope. This "smooths out" the problem, making it more amenable to gradient-based methods.
  • Alternating Updates: The algorithm alternates between updating the upper-level variable ($x$) and the lower-level variable ($y$). Crucially, it uses an inner loop to find an "inexact" estimate of the lower-level solution that only needs to satisfy a verifiable accuracy criterion, rather than being perfect.
  • Feasibility Correction Procedure: To prevent the algorithm from drifting away from the true solution set of the follower, the authors include a "safety check." If the current iterates look like they are approaching an infeasible point, a correction step is triggered to pull them back toward the lower-level optimal set.

Datasets

The authors evaluated AGILS on two primary benchmarks:

  1. Synthetic Toy Example: A specifically designed $n$-dimensional problem ($n=200$ and $n=600$) where the optimal solution is known, allowing for precise error measurement.
  2. Sparse Group Lasso: A hyperparameter selection problem using synthetic datasets (up to $m=10,500$ features). This model is a classic example of a "convex composite" lower-level problem that is non-smooth and lacks strong convexity, making it a perfect stress test for the algorithm.

Key Insights and Ideas

  • Decoupling Nonsmoothness: By using an alternating gradient approach, the algorithm decouples the nonsmooth parts of the lower-level objective (like $L_1$ regularization) from the upper-level updates. This allows it to handle complex regularizers that trip up other methods.
  • The Power of Inexactness: The paper proves that you don't need to solve the follower's problem to high precision in every step to guarantee convergence to a KKT (stationary) point. This is the "aha moment" for efficiency—doing less work per iteration still leads to the right destination.
  • Theoretical Rigor: Unlike many heuristic bilevel methods, the authors provide a full convergence analysis. They show that under the Kurdyka-Łojasiewicz (KL) property—a condition satisfied by most practical ML functions—the sequence of iterates actually converges to a specific solution.

Key Results

  • Speed and Accuracy: In the toy example, AGILS was significantly faster than competitors. For $n=600$, AGILS took 0.14 seconds to reach zero error, while the next best gradient-based method (MEHA) took 0.48 seconds, and others like VF-iDCA took over 2 seconds.
  • Robustness in Hyperparameter Tuning: On the Sparse Group Lasso task, AGILS consistently achieved lower validation errors than standard methods like Grid Search, Random Search, and Bayesian Optimization (TPE), while being much faster than implicit differentiation methods (IGJO).
  • Scalability: The algorithm scaled gracefully to high-dimensional problems, solving a problem with over 10,000 features in roughly 13 minutes on a standard laptop—a task that would be prohibitive for many traditional bilevel solvers.

Limitations and Future Work

  • Convexity Constraint: The current theory and algorithm specifically target problems where the lower-level objective is convex. Extending this to non-convex lower-level problems (like deep neural networks) remains a significant challenge.
  • Parameter Sensitivity: While AGILS is more robust than some single-loop methods, it still involves several hyperparameters (penalty parameters, relaxation constants) that might require tuning for optimal performance on new problem classes.
  • The "Inactive" Correction: Interestingly, in their experiments, the feasibility correction procedure was rarely triggered. While this suggests the main algorithm is very stable, future work could investigate specific "pathological" cases where this correction becomes essential.

Summary updated

Abstract

In this paper, we study a class of bilevel optimization problems where the lower-level problem is a convex composite optimization model, which arises in various applications, including bilevel hyperparameter selection for regularized regression models. To solve these problems, we propose an Alternating Gradient-type algorithm with Inexact Lower-level Solutions (AGILS) based on a Moreau envelope-based reformulation of the bilevel optimization problem. The proposed algorithm does not require exact solutions of the lower-level problem at each iteration, improving computational efficiency. We prove the convergence of AGILS to stationary points and, under the Kurdyka-Łojasiewicz (KL) property, establish its sequential convergence. Numerical experiments, including a toy example and a bilevel hyperparameter selection problem for the sparse group Lasso model, demonstrate the effectiveness of the proposed AGILS.
BibTeX
@inproceedings{bai2026alternating,
  author = {Xiaoning Bai and Shangzhi Zeng and Adam Zhang and L. Zhang},
  title = {{Alternating Gradient-Type Algorithm for Bilevel Optimization with Inexact Lower-Level Solutions via Moreau Envelope–Based Reformulation}},
  booktitle = {SIAM},
  year = {2026},
  doi = {10.1137/24m1721049},
}
Figure