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-order smoothness conditions, our deterministic method can escape saddle points by injecting noise, and can be accelerated to achieve a faster rate of $\tilde {\mathcal{O}}(\epsilon^{-1.75})$ using Nesterov's momentum.
| Comments: | JMLR 2025; fix a bug in the proof in Appendix E compared to the journal version |
| Subjects: | Optimization and Control (math.OC); Machine Learning (cs.LG) |
| Cite as: | arXiv:2306.14853 [math.OC] |
| (or arXiv:2306.14853v5 [math.OC] for this version) | |
| https://doi.org/10.48550/arXiv.2306.14853 arXiv-issued DOI via DataCite |
From: Lesi Chen [view email]
[v1]
Mon, 26 Jun 2023 17:07:54 UTC (69 KB)
[v2]
Mon, 28 Aug 2023 04:46:52 UTC (88 KB)
[v3]
Fri, 30 May 2025 03:23:29 UTC (132 KB)
[v4]
Tue, 24 Mar 2026 09:14:23 UTC (123 KB)
[v5]
Mon, 25 May 2026 07:26:53 UTC (123 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。