Finite-sum Composition Optimization via Variance Reduced Gradient Descent

Xiangru Lian, Mengdi Wang, Ji Liu
Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, PMLR 54:1159-1167, 2017.

Abstract

The stochastic composition optimization proposed recently by Wang et al. [2014] minimizes the objective with the composite expectation form: $\min_x (\mathbbE_iF_i ∘\mathbbE_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) := \frac1n \sum_i = 1^n F_i \left( \frac1m \sum_j = 1^m G_j (x) \right)$. In this paper, two algorithms are proposed 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v54-lian17a, title = {{Finite-sum Composition Optimization via Variance Reduced Gradient Descent}}, author = {Lian, Xiangru and Wang, Mengdi and Liu, Ji}, booktitle = {Proceedings of the 20th International Conference on Artificial Intelligence and Statistics}, pages = {1159--1167}, year = {2017}, editor = {Singh, Aarti and Zhu, Jerry}, volume = {54}, series = {Proceedings of Machine Learning Research}, month = {20--22 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v54/lian17a/lian17a.pdf}, url = {https://proceedings.mlr.press/v54/lian17a.html}, abstract = {The stochastic composition optimization proposed recently by Wang et al. [2014] minimizes the objective with the composite expectation form: $\min_x (\mathbbE_iF_i ∘\mathbbE_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) := \frac1n \sum_i = 1^n F_i \left( \frac1m \sum_j = 1^m G_j (x) \right)$. In this paper, two algorithms are proposed 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. } }
Endnote
%0 Conference Paper %T Finite-sum Composition Optimization via Variance Reduced Gradient Descent %A Xiangru Lian %A Mengdi Wang %A Ji Liu %B Proceedings of the 20th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2017 %E Aarti Singh %E Jerry Zhu %F pmlr-v54-lian17a %I PMLR %P 1159--1167 %U https://proceedings.mlr.press/v54/lian17a.html %V 54 %X The stochastic composition optimization proposed recently by Wang et al. [2014] minimizes the objective with the composite expectation form: $\min_x (\mathbbE_iF_i ∘\mathbbE_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) := \frac1n \sum_i = 1^n F_i \left( \frac1m \sum_j = 1^m G_j (x) \right)$. In this paper, two algorithms are proposed 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.
APA
Lian, X., Wang, M. & Liu, J.. (2017). Finite-sum Composition Optimization via Variance Reduced Gradient Descent. Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 54:1159-1167 Available from https://proceedings.mlr.press/v54/lian17a.html.

Related Material