FAI-Seminar官网:www.fai-seminar.ac.cn
Near-Optimal Nonconvex-Strongly-Convex Bilevel Optimization with Fully First-Order Oracles
讲座摘要:Bilevel optimization has wide applications such as hyperparameter tuning, neural architecture search, and meta-learning. Designing efficient algorithms for bilevel optimization is challenging because the lower-level problem defines a feasibility set implicitly via another optimization problem. In this work, we consider one tractable case when the lower-level problem is strongly convex. Recent works show that with a Hessian-vector product oracle, one can provably find an ε-first-order stationary point within O(1/ε^2 ) oracle calls. However, Hessian-vector product 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 O(1/ε^3) . In this work, we provide a tighter analysis demonstrating that this method can converge at the near-optimal O(1/ε^2 ) rate as second-order methods. Our analysis further leads to simple first-order algorithms that achieve similar convergence rates for finding second-order stationary points and for distributed bilevel problems. Joint work with Yaohua Ma and Jingzhao Zhang.
讲者信息:陈乐偲,本科毕业于复旦大学大数据学院,目前清华大学交叉信息研究院一年级博士生在读,指导教师为张景昭助理教授。研究方向为优化理论。