# Duality-free Methods for Stochastic Composition Optimization

arXiv: https://arxiv.org/abs/1710.09554 · HTML: https://mlsanity.com/paper/1710.09554/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Oct 2017.

## Built on by (most cited first, 3 of 3)

- [Stochastic Optimization of Areas Under Precision-Recall Curves with Provable Convergence](https://mlsanity.com/paper/2104.08736/) (2021)
- [Momentum Accelerates the Convergence of Stochastic AUPRC Maximization](https://mlsanity.com/paper/2107.01173/) (2021)
- [Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function](https://mlsanity.com/paper/2310.11866/) (2023)

## Abstract (arXiv)

We consider the composition optimization with two expected-value functions in the form of frac1nsumnolimitsi = 1n Fi(frac1msumnolimitsj = 1m Gj(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 frac1msumnolimitsj = 1m Gj(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. We prove the linear convergence rate not only for the convex composition problem, but also for the case that the individual outer functions are non-convex while the objective function is strongly-convex. We also provide the results of experiments that show the effectiveness of our proposed methods.