Dualityfree Methods for Stochastic Composition Optimization.

Abstract

In this paper, we consider the composition optimization with two expected-value functions in the form of (1/n)∑_{i = 1}ⁿ F_i((1/m)∑_{j = 1}^m G_j(x))+R(x) , which formulates many important problems in statistical learning and machine learning such as solving Bellman equations in reinforcement learning and nonlinear embedding. Full gradient- or classical stochastic gradient descent-based optimization algorithms are unsuitable or computationally expensive to solve this problem due to the inner expectation (1/m)∑_{j = 1}^m G_j(x) . We propose a dualityfree-based stochastic composition method that combines the variance reduction methods to address the stochastic composition problem. We apply the stochastic variance reduction gradient- and stochastic average gradient algorithm-based methods to estimate the inner function and the dualityfree method to estimate the outer function. We prove the linear convergence rate not only for the convex composition problem but also for the case that the individual outer functions are nonconvex, while the objective function is strongly convex. We also provide the results of experiments that show the effectiveness of our proposed methods.