Finite-sum Composition Optimization via Variance Reduced Gradient Descent

MaRDI QIDQ6278658zbMATH OpenFDO

Authors Xiangru Lian, Mengdi Wang, Ji Liu

Publication date 14 October 2016

Abstract: The stochastic composition optimization proposed recently by Wang et al. [2014] minimizes the objective with the compositional expectation form: $mi{n}_x(mathbb{E}_i{F}_{i}circmathbb{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) ight). ] We propose two algorithms to solve this problem by combining the stochastic compositional gradient descent (SCGD) and the stochastic variance reduced gradient (SVRG) technique. A constant linear convergence rate is proved for strongly convex optimization, which substantially improves the sublinear rate $O(K^{-0.8})$ of the best known algorithm.

This page was built for publication: Finite-sum Composition Optimization via Variance Reduced Gradient Descent

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