Timezone: »

 
Poster
Efficient Smooth Non-Convex Stochastic Compositional Optimization via Stochastic Recursive Gradient Descent
Wenqing Hu · Chris Junchi Li · Xiangru Lian · Ji Liu · Angela Yuan

Thu Dec 12 10:45 AM -- 12:45 PM (PST) @ East Exhibition Hall B + C #197
in Optimization -- Non-Convex Optimization »
Stochastic compositional optimization arises in many important machine learning tasks such as reinforcement learning and portfolio management. The objective function is the composition of two expectations of stochastic functions, and is more challenging to optimize than vanilla stochastic optimization problems. In this paper, we investigate the stochastic compositional optimization in the general smooth non-convex setting. We employ a recently developed idea of \textit{Stochastic Recursive Gradient Descent} to design a novel algorithm named SARAH-Compositional, and prove a sharp Incremental First-order Oracle (IFO) complexity upper bound for stochastic compositional optimization: $\mathcal{O}((n+m)^{1/2} \varepsilon^{-2})$ in the finite-sum case and $\mathcal{O}(\varepsilon^{-3})$ in the online case. Such a complexity is known to be the best one among IFO complexity results for non-convex stochastic compositional optimization. Numerical experiments validate the superior performance of our algorithm and theory.
Keywords: Convex Optimization · Optimization · Optimization
[ Paper]  [ Poster] 

Author Information

Wenqing Hu (Missouri S&T)
Chris Junchi Li (Tecent AI Lab)
Xiangru Lian (University of Rochester)
Ji Liu (Kwai Inc.)
Angela Yuan (Peking University)

More from the Same Authors