Finite-sum composition optimization via variance reduced gradient descent

Xiangru Lian; Mengdi Wang; Ji Liu

Finite-sum composition optimization via variance reduced gradient descent

Xiangru Lian, Mengdi Wang, Ji Liu

Research output: Contribution to conference › Paper › peer-review

Abstract

The stochastic composition optimization proposed recently by Wang et al. [2014] minimizes the objective with the compositional expectation form: min_x (E_iF_i o E_jG_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: (Formula presented.). 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.

Original language	English (US)
State	Published - Jan 1 2017
Event	20th International Conference on Artificial Intelligence and Statistics, AISTATS 2017 - Fort Lauderdale, United States Duration: Apr 20 2017 → Apr 22 2017

Conference

Conference	20th International Conference on Artificial Intelligence and Statistics, AISTATS 2017
Country/Territory	United States
City	Fort Lauderdale
Period	4/20/17 → 4/22/17

All Science Journal Classification (ASJC) codes

Artificial Intelligence
Statistics and Probability

Cite this

@conference{8f4f5c174f3b46f480d50b68855d73bf,

title = "Finite-sum composition optimization via variance reduced gradient descent",

abstract = "The stochastic composition optimization proposed recently by Wang et al. [2014] minimizes the objective with the compositional expectation form: minx (EiFi o EjGj)(x). It summarizes many important applications in machine learning, statistics, and finance. In this paper, we consider the finite-sum scenario for composition optimization: (Formula presented.). 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.",

author = "Xiangru Lian and Mengdi Wang and Ji Liu",

year = "2017",

month = jan,

day = "1",

language = "English (US)",

note = "20th International Conference on Artificial Intelligence and Statistics, AISTATS 2017 ; Conference date: 20-04-2017 Through 22-04-2017",

}

TY - CONF

T1 - Finite-sum composition optimization via variance reduced gradient descent

AU - Lian, Xiangru

AU - Wang, Mengdi

AU - Liu, Ji

PY - 2017/1/1

Y1 - 2017/1/1

N2 - The stochastic composition optimization proposed recently by Wang et al. [2014] minimizes the objective with the compositional expectation form: minx (EiFi o EjGj)(x). It summarizes many important applications in machine learning, statistics, and finance. In this paper, we consider the finite-sum scenario for composition optimization: (Formula presented.). 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.

AB - The stochastic composition optimization proposed recently by Wang et al. [2014] minimizes the objective with the compositional expectation form: minx (EiFi o EjGj)(x). It summarizes many important applications in machine learning, statistics, and finance. In this paper, we consider the finite-sum scenario for composition optimization: (Formula presented.). 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.

UR - http://www.scopus.com/inward/record.url?scp=85059349023&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85059349023&partnerID=8YFLogxK

M3 - Paper

T2 - 20th International Conference on Artificial Intelligence and Statistics, AISTATS 2017

Y2 - 20 April 2017 through 22 April 2017

ER -

Finite-sum composition optimization via variance reduced gradient descent

Abstract

Conference

All Science Journal Classification (ASJC) codes

Other files and links

Fingerprint

Cite this