A Fully First-Order Method for Stochastic Bilevel Optimization
This addresses the problem of efficient optimization in bilevel settings for machine learning practitioners, offering a novel method that is incremental in improving computational efficiency over existing approaches.
The paper tackles stochastic bilevel optimization by proposing a fully first-order method (F2SA) that avoids expensive Hessian calculations, achieving convergence to an ε-stationary solution with iteration complexities of ε^{-7/2}, ε^{-5/2}, and ε^{-3/2} under different noise settings, and shows superior practical performance on MNIST data-hypercleaning experiments.
We consider stochastic unconstrained bilevel optimization problems when only the first-order gradient oracles are available. While numerous optimization methods have been proposed for tackling bilevel problems, existing methods either tend to require possibly expensive calculations regarding Hessians of lower-level objectives, or lack rigorous finite-time performance guarantees. In this work, we propose a Fully First-order Stochastic Approximation (F2SA) method, and study its non-asymptotic convergence properties. Specifically, we show that F2SA converges to an $ε$-stationary solution of the bilevel problem after $ε^{-7/2}, ε^{-5/2}$, and $ε^{-3/2}$ iterations (each iteration using $O(1)$ samples) when stochastic noises are in both level objectives, only in the upper-level objective, and not present (deterministic settings), respectively. We further show that if we employ momentum-assisted gradient estimators, the iteration complexities can be improved to $ε^{-5/2}, ε^{-4/2}$, and $ε^{-3/2}$, respectively. We demonstrate even superior practical performance of the proposed method over existing second-order based approaches on MNIST data-hypercleaning experiments.