A Fully First-Order Method for Stochastic Bilevel Optimization

Jeongyeol Kwon, Dohyun Kwon, Stephen Wright, Robert Nowak

Research output: Contribution to journalConference articlepeer-review

2 Scopus citations


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.

Original languageEnglish
Pages (from-to)18083-18113
Number of pages31
JournalProceedings of Machine Learning Research
StatePublished - 2023
Event40th International Conference on Machine Learning, ICML 2023 - Honolulu, United States
Duration: 23 Jul 202329 Jul 2023


Dive into the research topics of 'A Fully First-Order Method for Stochastic Bilevel Optimization'. Together they form a unique fingerprint.

Cite this