{"ID":2824049,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.24291","arxiv_id":"2512.24291","title":"Adaptive Algorithms for Nonconvex Bilevel Optimization under PŁ Conditions","abstract":"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.","short_abstract":"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 computatio...","url_abs":"https://arxiv.org/abs/2512.24291","url_pdf":"https://arxiv.org/pdf/2512.24291v1","authors":"[\"Xu Shi\",\"Yinglin Du\",\"Rufeng Xiao\",\"Rujun Jiang\"]","published":"2025-12-30T15:28:37Z","proceeding":"math.OC","tasks":"[\"math.OC\"]","methods":"[]","has_code":false}