Duality-free Methods for Stochastic Composition Optimization

Understand

We consider the composition optimization with two expected-value functions in the form of $\frac{1}{n}\sum\nolimits_{i = 1}^n F_i(\frac{1}{m}\sum\nolimits_{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 $\frac{1}{m}\sum\nolimits_{j = 1}^m G_j(x)$.
• We propose a duality-free based stochastic composition method that combines variance reduction methods to address the stochastic composition problem.
• We apply SVRG and SAGA based methods to estimate the inner function, and duality-free method to estimate the outer function.