Timezone: »

 
Poster
A Near-Optimal Algorithm for Stochastic Bilevel Optimization via Double-Momentum
Prashant Khanduri · Siliang Zeng · Mingyi Hong · Hoi-To Wai · Zhaoran Wang · Zhuoran Yang

Thu Dec 09 08:30 AM -- 10:00 AM (PST) @
in Poster Session 6 »
This paper proposes a new algorithm -- the \underline{S}ingle-timescale Do\underline{u}ble-momentum \underline{St}ochastic \underline{A}pprox\underline{i}matio\underline{n} (SUSTAIN) -- for tackling stochastic unconstrained bilevel optimization problems. We focus on bilevel problems where the lower level subproblem is strongly-convex and the upper level objective function is smooth. Unlike prior works which rely on \emph{two-timescale} or \emph{double loop} techniques, we design a stochastic momentum-assisted gradient estimator for both the upper and lower level updates. The latter allows us to control the error in the stochastic gradient updates due to inaccurate solution to both subproblems. If the upper objective function is smooth but possibly non-convex, we show that {SUSTAIN}~requires $O(\epsilon^{-3/2})$ iterations (each using $O(1)$ samples) to find an $\epsilon$-stationary solution. The $\epsilon$-stationary solution is defined as the point whose squared norm of the gradient of the outer function is less than or equal to $\epsilon$. The total number of stochastic gradient samples required for the upper and lower level objective functions matches the best-known complexity for single-level stochastic gradient algorithms. We also analyze the case when the upper level objective function is strongly-convex.
Keywords: Optimization

Author Information

Prashant Khanduri (University of Minnesota)
Siliang Zeng (University of Minnesota, Twin Cities)
Mingyi Hong (University of Minnesota)
Hoi-To Wai (The Chinese University of Hong Kong)
Zhaoran Wang (Princeton University)
Zhuoran Yang (Princeton)

More from the Same Authors