On Finding Small Hyper-Gradients in Bilevel Optimization: Hardness Results and Improved Analysis
Bilevel optimization reveals the inner structure of otherwise oblique optimization problems, such as hyperparameter tuning, neural architecture search, and meta-learning. A common goal in bilevel optimization is to minimize a hyper-objective that implicitly depends on the solution set of the lower-level function. Although this hyper-objective approach is widely used, its theoretical properties have not been thoroughly investigated in cases where the lower-level functions lack strong convexity. In this work, we first provide hardness results to show that the goal of finding stationary points of the hyper-objective for nonconvex-convex bilevel optimization can be intractable for zero-respecting algorithms. Then we study a class of tractable nonconvex-nonconvex bilevel problems when the lower-level function satisfies the Polyak-{\L}ojasiewicz (PL) condition. We show a simple first-order algorithm can achieve better complexity bounds of $\tilde{\mathcal{O}}(\epsilon^{-2})$, $\tilde{\mathcal{O}}(\epsilon^{-4})$ and $\tilde{\mathcal{O}}(\epsilon^{-6})$ in the deterministic, partially stochastic, and fully stochastic setting respectively. The complexities in the first two cases are optimal up to logarithmic factors.
Code (0)
등록된 구현이 없습니다.
Tasks
Bilevel OptimizationMeta-LearningNeural Architecture SearchSimilar Papers 제목 키워드 기반
Bilevel Optimization with Lower-Level Uniform Convexity: Theory and Algorithm
Bilevel optimization is a hierarchical framework where an upper-level optimization problem is constrained by a lower-level problem, commonly used in machine learning applications such as hyperparameter optimization. Exis…
Hyperparameter OptimizationBilevel OptimizationEnhanced Bilevel Optimization via Bregman Distance
Bilevel optimization has been recently used in many machine learning problems such as hyperparameter optimization, policy optimization, and meta learning. Although many bilevel optimization methods have been proposed, th…
Bilevel OptimizationHyperparameter OptimizationMeta-LearningRepresentation LearningEfficient Curvature-Aware Hypergradient Approximation for Bilevel Optimization
Bilevel optimization is a powerful tool for many machine learning problems, such as hyperparameter optimization and meta-learning. Estimating hypergradients (also known as implicit gradients) is crucial for developing gr…
Bilevel OptimizationHyperparameter OptimizationMeta-LearningBi-Level Policy Optimization with Nyström Hypergradients
The dependency of the actor on the critic in actor-critic (AC) reinforcement learning means that AC can be characterized as a bilevel optimization (BLO) problem, also called a Stackelberg game. This characterization moti…
Bilevel Optimizationcontinuous-controlContinuous ControlA Communication and Computation Efficient Fully First-order Method for Decentralized Bilevel Optimization
Bilevel optimization, crucial for hyperparameter tuning, meta-learning and reinforcement learning, remains less explored in the decentralized learning paradigm, such as decentralized federated learning (DFL). Typically, …
Bilevel OptimizationFederated LearningMeta-Learning