# Perturbed Gradient Descent via Convex Quadratic Approximation for Nonconvex Bilevel Optimization

arXiv: https://arxiv.org/abs/2504.17215 · HTML: https://mlsanity.com/paper/2504.17215/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Apr 2025.

## Built on by (most cited first, 2 of 2)

- [Sequential QCQP for Bilevel Optimization with Line Search](https://mlsanity.com/paper/2505.14647/) (2025)
- [Learning to Solve Constrained Bilevel Control Co-Design Problems](https://mlsanity.com/paper/2507.09050/) (2025)

## Abstract (arXiv)

Bilevel optimization is a fundamental tool in hierarchical decision-making and has been widely applied to machine learning tasks such as hyperparameter tuning, meta-learning, and continual learning. While significant progress has been made in bilevel optimization, existing methods predominantly focus on the nonconvex-strongly convex, or the nonconvex-PL settings, leaving the more general nonconvex-nonconvex framework underexplored. In this paper, we address this gap by developing an efficient gradient-based method inspired by the recently proposed Relaxed Gradient Flow (RXGF) framework with a continuous-time dynamic. In particular, we introduce a discretized variant of RXGF and formulate convex quadratic program subproblems with closed-form solutions. We provide a rigorous convergence analysis, demonstrating that under the existence of a KKT point and a regularity assumption (lower-level gradient PL assumption), our method achieves an iteration complexity of O(1/ε1.5) in terms of the squared norm of the KKT residual for the reformulated problem. Moreover, even in the absence of the regularity assumption, we establish an iteration complexity of O(1/ε3) for the same metric. Through extensive numerical experiments on convex and nonconvex synthetic benchmarks and a hyper-data cleaning task, we illustrate the efficiency and scalability of our approach.