Adaptive Algorithms for Nonconvex Bilevel Optimization under PŁ Conditions
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911347143344128 |
|---|---|
| author | Shi, Xu Du, Yinglin Xiao, Rufeng Jiang, Rujun |
| author_facet | Shi, Xu Du, Yinglin Xiao, Rufeng Jiang, Rujun |
| contents | Existing methods for nonconvex bilevel optimization (NBO) require prior knowledge of first- and second-order problem-specific parameters (e.g., Lipschitz constants and the Polyak-Łojasiewicz (PŁ) parameters) to set step sizes, a requirement that poses practical limitations when such parameters are unknown or computationally expensive. We introduce the Adaptive Fully First-order Bilevel Approximation (AF${}^2$BA) algorithm and its accelerated variant, A${}^2$F${}^2$BA, for solving NBO problems under the PŁ conditions. To our knowledge, these are the first methods to employ fully adaptive step size strategies, eliminating the need for any problem-specific parameters in NBO. We prove that both algorithms achieve $\mathcal{O}(1/ε^2)$ iteration complexity for finding an $ε$-stationary point, matching the iteration complexity of existing well-tuned methods. Furthermore, we show that A${}^2$F${}^2$BA enjoys a near-optimal first-order oracle complexity of $\tilde{\mathcal{O}}(1/ε^2)$, matching the oracle complexity of existing well-tuned methods, and aligning with the complexity of gradient descent for smooth nonconvex single-level optimization when ignoring the logarithmic factors. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_24291 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Adaptive Algorithms for Nonconvex Bilevel Optimization under PŁ Conditions Shi, Xu Du, Yinglin Xiao, Rufeng Jiang, Rujun Optimization and Control Existing methods for nonconvex bilevel optimization (NBO) require prior knowledge of first- and second-order problem-specific parameters (e.g., Lipschitz constants and the Polyak-Łojasiewicz (PŁ) parameters) to set step sizes, a requirement that poses practical limitations when such parameters are unknown or computationally expensive. We introduce the Adaptive Fully First-order Bilevel Approximation (AF${}^2$BA) algorithm and its accelerated variant, A${}^2$F${}^2$BA, for solving NBO problems under the PŁ conditions. To our knowledge, these are the first methods to employ fully adaptive step size strategies, eliminating the need for any problem-specific parameters in NBO. We prove that both algorithms achieve $\mathcal{O}(1/ε^2)$ iteration complexity for finding an $ε$-stationary point, matching the iteration complexity of existing well-tuned methods. Furthermore, we show that A${}^2$F${}^2$BA enjoys a near-optimal first-order oracle complexity of $\tilde{\mathcal{O}}(1/ε^2)$, matching the oracle complexity of existing well-tuned methods, and aligning with the complexity of gradient descent for smooth nonconvex single-level optimization when ignoring the logarithmic factors. |
| title | Adaptive Algorithms for Nonconvex Bilevel Optimization under PŁ Conditions |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2512.24291 |