Efficient Gradient Approximation Method for Constrained Bilevel Optimization

Siyuan Xu, Minghui Zhu

Abstract

Bilevel optimization has been developed for many machine learning tasks with large-scale and high-dimensional data. This paper considers a constrained bilevel optimization problem, where the lower-level optimization problem is convex with equality and inequality constraints and the upper-level optimization problem is non-convex. The overall objective function is non-convex and non-differentiable. To solve the problem, we develop a gradient-based approach, called gradient approximation method, which determines the descent direction by computing several representative gradients of the objective function inside a neighborhood of the current estimate. We show that the algorithm asymptotically converges to the set of Clarke stationary points, and demonstrate the efficacy of the algorithm by the experiments on hyperparameter optimization and meta-learning.

Introduction: The Challenge of Non-Smoothness

Bilevel optimization involves two nested problems: an "upper-level" task that depends on the optimal solution of a "lower-level" task. This structure is ubiquitous in machine learning, particularly for hyperparameter tuning—where the upper level minimizes validation loss and the lower level minimizes training loss—and meta-learning.

A major challenge arises when the lower-level problem includes constraints, such as inequality or equality bounds. In these scenarios, the overall objective function often becomes non-differentiable. Standard gradient-based methods assume smoothness; when they encounter "kinks" in the optimization landscape, they can oscillate or fail to converge. While gradient sampling methods can handle non-smoothness, they are often computationally prohibitive for high-dimensional models because they require solving the lower-level problem numerous times per step.

The Gradient Approximation Method (GAM)

The authors propose the Gradient Approximation Method (GAM) to address these issues efficiently. Their approach is built on several theoretical innovations:

  1. Identifying the "Kinks": The paper proves that non-differentiability occurs specifically at points where the "Strict Complementarity Slackness Condition" (SCSC) is violated. This happens when a constraint is exactly on the boundary of being active or inactive.
  2. Representative Gradients: Instead of massive random sampling, GAM identifies a small set of "representative gradients." If the current point is near a non-differentiable boundary, the algorithm calculates gradients for the different "modes" (e.g., one where the constraint is active and one where it isn't).
  3. Clarke Subdifferential Approximation: These representative gradients are used to approximate the Clarke subdifferential—a generalization of the gradient for non-smooth functions.
  4. Descent Direction: The algorithm finds the vector with the smallest norm within the convex hull of these representative gradients, serving as a reliable descent direction for a line search.
Visualization of constraint activity and the resulting non-differentiability (kinks) in the optimal solution $y^*(x)$.

By leveraging the KKT conditions of the lower-level problem, GAM can analytically derive these representative gradients. This turns a "black-box" sampling problem into a "white-box" structural calculation, significantly improving efficiency.

Experimental Evaluation and Results

The authors evaluated GAM across several machine learning tasks, including Hyperparameter Optimization (HO) for Support Vector Machines (SVM) and data hyper-cleaning. On the UCI Breast Cancer dataset with 40% label noise, GAM converged faster than standard gradient descent, reaching ~96.2% accuracy—nearly matching the 96.5% accuracy of models trained on perfectly clean data.

In meta-learning experiments using the MetaOptNet framework on CIFAR-FS and FC100 datasets, GAM achieved faster convergence and higher final test accuracy than traditional direct gradient descent. This suggests that the "representative gradient" approach is superior for the complex landscapes of few-shot learning.

Performance of GAM on Kernelized SVM hyperparameter optimization, showing steady improvement in accuracy over running time.

Key Insights and Limitations

A central insight of this work is the mathematical link between lower-level constraint transitions and upper-level non-differentiability. This allows the algorithm to predict exactly when multiple gradients are needed. Furthermore, explicitly accounting for the non-smooth nature of the problem leads to more stable convergence in complex landscapes.

However, some limitations remain. The theory assumes the lower-level problem has a unique optimal solution; multiple solutions would introduce significant complexity. Additionally, calculating representative gradients requires computing Hessians of the lower-level objective and constraints, which can be a bottleneck for very large neural networks. Future work may explore "inexact" versions of GAM to improve scalability for billion-parameter models.

Summary updated

Abstract

Bilevel optimization has been developed for many machine learning tasks with large-scale and high-dimensional data. This paper considers a constrained bilevel optimization problem, where the lower-level optimization problem is convex with equality and inequality constraints and the upper-level optimization problem is non-convex. The overall objective function is non-convex and non-differentiable. To solve the problem, we develop a gradient-based approach, called gradient approximation method, which determines the descent direction by computing several representative gradients of the objective function inside a neighborhood of the current estimate. We show that the algorithm asymptotically converges to the set of Clarke stationary points, and demonstrate the efficacy of the algorithm by the experiments on hyperparameter optimization and meta-learning.
BibTeX
@inproceedings{xu2023efficient,
  author = {Siyuan Xu and Minghui Zhu},
  title = {{Efficient Gradient Approximation Method for Constrained Bilevel Optimization}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  url = {https://openreview.net/forum?id=kFyS4I70Zv},
}
Figure