An Optimal Algorithm for Stochastic Three-Composite Optimization

Renbo Zhao, William B. Haskell, Vincent Y. F. Tan
Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, PMLR 89:428-437, 2019.

Abstract

We develop an optimal primal-dual first-order algorithm for a class of stochastic three-composite convex minimization problems. The convergence rate of our method not only improves upon the existing methods, but also matches a lower bound derived for all first-order methods that solve this problem. We extend our proposed algorithm to solve a composite stochastic program with any finite number of nonsmooth functions. In addition, we generalize an optimal stochastic alternating direction method of multipliers (SADMM) algorithm proposed for the two-composite case to solve this problem, and establish its connection to our optimal primal-dual algorithm. We perform extensive numerical experiments on a variety of machine learning applications to demonstrate the superiority of our method via-a-vis the state-of-the-art.

Cite this Paper

BibTeX
@InProceedings{pmlr-v89-zhao19a, title = {An Optimal Algorithm for Stochastic Three-Composite Optimization}, author = {Zhao, Renbo and Haskell, William B. and Tan, Vincent Y. F.}, booktitle = {Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics}, pages = {428--437}, year = {2019}, editor = {Chaudhuri, Kamalika and Sugiyama, Masashi}, volume = {89}, series = {Proceedings of Machine Learning Research}, month = {16--18 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v89/zhao19a/zhao19a.pdf}, url = {https://proceedings.mlr.press/v89/zhao19a.html}, abstract = {We develop an optimal primal-dual first-order algorithm for a class of stochastic three-composite convex minimization problems. The convergence rate of our method not only improves upon the existing methods, but also matches a lower bound derived for all first-order methods that solve this problem. We extend our proposed algorithm to solve a composite stochastic program with any finite number of nonsmooth functions. In addition, we generalize an optimal stochastic alternating direction method of multipliers (SADMM) algorithm proposed for the two-composite case to solve this problem, and establish its connection to our optimal primal-dual algorithm. We perform extensive numerical experiments on a variety of machine learning applications to demonstrate the superiority of our method via-a-vis the state-of-the-art.} }
Endnote
%0 Conference Paper %T An Optimal Algorithm for Stochastic Three-Composite Optimization %A Renbo Zhao %A William B. Haskell %A Vincent Y. F. Tan %B Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Masashi Sugiyama %F pmlr-v89-zhao19a %I PMLR %P 428--437 %U https://proceedings.mlr.press/v89/zhao19a.html %V 89 %X We develop an optimal primal-dual first-order algorithm for a class of stochastic three-composite convex minimization problems. The convergence rate of our method not only improves upon the existing methods, but also matches a lower bound derived for all first-order methods that solve this problem. We extend our proposed algorithm to solve a composite stochastic program with any finite number of nonsmooth functions. In addition, we generalize an optimal stochastic alternating direction method of multipliers (SADMM) algorithm proposed for the two-composite case to solve this problem, and establish its connection to our optimal primal-dual algorithm. We perform extensive numerical experiments on a variety of machine learning applications to demonstrate the superiority of our method via-a-vis the state-of-the-art.
APA
Zhao, R., Haskell, W.B. & Tan, V.Y.F.. (2019). An Optimal Algorithm for Stochastic Three-Composite Optimization. Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 89:428-437 Available from https://proceedings.mlr.press/v89/zhao19a.html.

Related Material