Timezone: »

 
Poster
A Fully First-Order Method for Stochastic Bilevel Optimization
Jeongyeol Kwon · Dohyun Kwon · Stephen Wright · Robert Nowak

Wed Jul 26 02:00 PM -- 03:30 PM (PDT) @ Exhibit Hall 1 #326
in Poster Session 3 »
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 $\epsilon$-stationary solution of the bilevel problem after $\epsilon^{-7/2}, \epsilon^{-5/2}$, and $\epsilon^{-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 $\epsilon^{-5/2}, \epsilon^{-4/2}$, and $\epsilon^{-3/2}$, respectively. We demonstrate even superior practical performance of the proposed method over existing second-order based approaches on MNIST data-hypercleaning experiments.

Author Information

Jeongyeol Kwon (University of Wisconsin-Madison)

I am currently a PostDoc at University of Wisconsin-Madison, working with Prof. Robert Nowak. Prior to joining UW-Madison, I received my Ph.D. in ECE department at UT Austin, where I had wonderful years of learning and working with my advisor Prof. Constantine Caramanis. I got my Bachelor’s Degree in Electrical and Computer Engineering from Seoul National University (SNU) in 2016.

Dohyun Kwon (University of Seoul)
Stephen Wright (University of Wisconsin-Madison)
Robert Nowak (University of Wisconsion-Madison)
Robert Nowak

Robert Nowak holds the Nosbusch Professorship in Engineering at the University of Wisconsin-Madison, where his research focuses on signal processing, machine learning, optimization, and statistics.

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors