Stochastic compositional gradient descent: algorithms for minimizing compositions of expected-value functions

DOI10.1007/S10107-016-1017-3MaRDI QIDQ507334zbMATH OpenOpenAlexFDO

Authors Mengdi Wang, Ethan X. Fang, Han Liu

Publication date 3 February 2017

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1411.3803

simulation convex optimization stochastic gradient statistical learning stochastic optimization sample complexity

Convex programming (90C25) Online algorithms; streaming algorithms (68W27) Large-scale problems in mathematical programming (90C06) Stochastic programming (90C15)

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

. 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

m a t h b f 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.

Recommendations

Cites work

Cited in

(38)

This page was built for publication: Stochastic compositional gradient descent: algorithms for minimizing compositions of expected-value functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q507334)