Finite-sum Composition Optimization via Variance Reduced Gradient Descent

Understand

The stochastic composition optimization proposed recently by Wang et al.

• [2014] minimizes the objective with the compositional expectation form: $\min_x~(\mathbb{E}_iF_i \circ \mathbb{E}_j G_j)(x).$ It summarizes many important applications in machine learning, statistics, and finance.
• In this paper, we consider the finite-sum scenario for composition optimization: \[\min_x f (x) := \frac{1}{n} \sum_{i = 1}^n F_i \left(\frac{1}{m} \sum_{j = 1}^m G_j (x) \right).
• \] We propose two algorithms to solve this problem by combining the stochastic compositional gradient descent (SCGD) and the stochastic variance reduced gradient (SVRG) technique.