  


Stochastic Compositional Gradient Descent: Algorithms for Minimizing Compositions of ExpectedValue Functions
Mengdi Wang (mengdiwprinceton.edu) Abstract: Classical stochastic gradient methods are well suited for minimizing expectedvalue objective functions. However, they do not apply to the minimization of a nonlinear function involving expected values or a composition of two expectedvalue 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 quasigradient 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 expectedvalue 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/2014 Modify/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  