- Stochastic Compositional Gradient Descent: Algorithms for Minimizing Compositions of Expected-Value Functions Mengdi Wang (mengdiwprinceton.edu) Ethan Fang (xingyuanprinceton.edu) Han Liu (hanliuprinceton.edu) Abstract: Classical stochastic gradient methods are well suited for minimizing expected-value objective functions. However, they do not apply to the minimization of a nonlinear function involving expected values or a composition of two expected-value functions, i.e., problems of the form $\min_x \E_v$f_v\big(\E_w [g_w(x)]\big)$$. In order to solve this stochastic composition problem, we propose a class of stochastic compositional gradient descent (SCGD) algorithms that can be viewed as stochastic versions of quasi-gradient method. SCGD update the solutions based on noisy sample gradients of $f_v,g_{w}$ and use an auxiliary variable to track the unknown quantity $\E_w$g_w(x)$$. We prove that the SCGD converge almost surely to an optimal solution for convex optimization problems, as long as such a solution exists. The convergence involves the interplay of two iterations with different time scales. For nonsmooth convex problems, the SCGD achieve a convergence rate of $\O(k^{-1/4})$ in the general case and $\O(k^{-2/3})$ in the strongly convex case, after taking $k$ samples. For smooth convex problems, the SCGD can be accelerated to converge at a rate of $\O(k^{-2/7})$ in the general case and $\O(k^{-4/5})$ in the strongly convex case. For nonconvex problems, we prove that any limit point generated by SCGD is a stationary point, for which we also provide the convergence rate analysis. Indeed, the stochastic setting where one wants to optimize compositions of expected-value functions is very common in practice. The proposed SCGD methods find wide applications in learning, estimation, dynamic programming, etc. Keywords: stochastic optimization, stochastic gradient, sample complexity, statistical learning, composition Category 1: Convex and Nonsmooth Optimization (Convex Optimization ) Category 2: Stochastic Programming Category 3: Applications -- Science and Engineering (Statistics ) Citation: Download: [PDF]Entry Submitted: 11/13/2014Entry Accepted: 11/14/2014Entry Last Modified: 09/01/2015Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Optmization Society.