[2306.14853] Near-Optimal Nonconvex-Strongly-Convex Bilevel Optimization with Fully First-Order Oracles

Mathematics > Optimization and Control arXiv:2306.14853 (math) [Submitted on 26 Jun 2023 (v1), last revised 24 Mar 2026 (this version, v4)] Title:Near-Optimal Nonconvex-Strongly-Convex Bilevel Optimization with Fully First-Order Oracles Authors:Lesi Chen, Yaohua Ma, Jingzhao Zhang View a PDF of the paper titled Near-Optimal Nonconvex-Strongly-Convex Bilevel Optimization with Fully First-Order Oracles, by Lesi Chen and 2 other authors View PDF Abstract:In this work, we consider bilevel optimization when the lower-level problem is strongly convex. Recent works show that with a Hessian-vector product (HVP) oracle, one can provably find an $\epsilon$-stationary point within ${\mathcal{O}}(\epsilon^{-2})$ oracle calls. However, the HVP oracle may be inaccessible or expensive in practice. Kwon et al. (ICML 2023) addressed this issue by proposing a first-order method that can achieve the same goal at a slower rate of $\tilde{\mathcal{O}}(\epsilon^{-3})$. In this paper, we incorporate a two-time-scale update to improve their method to achieve the near-optimal $\tilde {\mathcal{O}}(\epsilon^{-2})$ first-order oracle complexity. Our analysis is highly extensible. In the stochastic setting, our algorithm can achieve the stochastic first-order oracle complexity of $\tilde {\mathcal{O}}(\epsilon^{-4})$ and $\tilde {\mathcal{O}}(\epsilon^{-6})$ when the stochastic noises are only in the upper-level objective and in both level objectives, respectively. When the objectives have higher-ord...