---
title: "Escaping Saddle Point Efficiently in Minimax and Bilevel Optimizations"
authors:
  - "Wenhan Xian"
  - "Feihu Huang"
  - "Heng Huang"
doi: "10.24963/ijcai.2025/741"
url: "https://ijcai.org/proceedings/2025/741"
pdf: "https://ijcai.org/proceedings/2025/0741.pdf"
venue: "Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence"
year: 2025
pages: "6659-6668"
track: "Main Track"
keywords:
  - "Machine Learning: ML: Optimization"
---

# Escaping Saddle Point Efficiently in Minimax and Bilevel Optimizations

Wenhan Xian, Feihu Huang, Heng Huang

*Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence*, pages 6659-6668. DOI: [10.24963/ijcai.2025/741](https://doi.org/10.24963/ijcai.2025/741)

## Abstract

Hierarchical optimization is attracting significant attentions as it can be applied to a broad range of machine learning tasks. Recently, many algorithms are proposed to improve the theoretical results of minimax and bilevel optimizations. Among these works, a core issue that has not been well studies is to escape saddle point and find local minimum. In this paper, thus, we investigate the methods to achieve second-order optimality for nonconvex minimax and bilevel optimization. Specifically, we propose a new algorithm named PRGDA without the computation of second order derivative of the primal function. In nonconvex-strongly-concave minimax optimization, we prove that our algorithm can find a second-order stationary point with the gradient complexity that matches state-of-the-art result to find first-order stationary point. To our best knowledge, PRGDA is the first stochastic algorithm that is guaranteed to obtain the second-order stationary point for nonconvex minimax problems. In nonconvex-strongly-convex bilevel optimization, our method also achieves better gradient complexity to find local minimum. Finally, we conduct two numerical experiments to validate the performance of our new method.