Optimizing complex nested problems with efficient stochastic methods
Optimal Stochastic Bilevel Optimization with First-Order Oracles
Machine Learning
Summary
Solving problems where one task depends on another can be tricky, especially when both have uncertain information. The authors study such nested problems, called bilevel optimization, where the outer problem is hard and the inner one easier. They developed a new method that updates all parts together efficiently, using clever tricks to estimate tricky math terms. They prove their method is as fast as possible for a wide class of problems, showing the limits of how well such methods can perform.
What this means in practice
- •For machine learning engineers: Achieve optimal training speeds when tuning nested models like hyperparameter optimization under noisy gradients.
- •For control system designers: Design algorithms for systems with layered objectives, ensuring efficiency despite uncertain measurements.
A theory result. No direct application yet.
Authors
Linxuan Pan, Junchi Yang
Abstract
We study nonconvex--strongly-convex bilevel optimization under a stochastic first-order oracle. We introduce MRT-FD, a single-loop first-order method that simultaneously tracks the upper-level variable, the lower-level solution, and the auxiliary response arising from implicit differentiation of the hyperobjective. MRT-FD performs one update of each variable per iteration and approximates the second-order derivative actions using order-$p$ finite differences. For any fixed finite smoothness order $p\ge1$ in the lower-level variable, MRT-FD finds an $\varepsilon$-stationary point using $\mathcal{O}(\varepsilon^{-4-2/p})$ stochastic gradient queries. We also prove a matching $Ω(\varepsilon^{-4-2/p})$ oracle lower bound. The lower-bound construction starts from a hard nonconvex minimization chain with a stronger stochastic oracle, and lifts it to a bilevel problem through a sinusoidal coupling with a scalar lower-level variable. Consequently, the dependence on $\varepsilon$ is optimal for every fixed finite $p$, closing the upper--lower complexity gap in this stochastic first-order oracle setting.