On Finding Small Hyper-Gradients in Bilevel Optimization: Hardness Results and Improved Analysis

Understand

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.