Stochastic Gauss-Newton Algorithms for Nonconvex Compositional Optimization

Quoc Tran-Dinh, Nhan Pham, Lam Nguyen
Proceedings of the 37th International Conference on Machine Learning, PMLR 119:9572-9582, 2020.

Abstract

We develop two new stochastic Gauss-Newton algorithms for solving a class of non-convex stochastic compositional optimization problems frequently arising in practice. We consider both the expectation and finite-sum settings under standard assumptions, and use both classical stochastic and SARAH estimators for approximating function values and Jacobians. In the expectation case, we establish $\BigO{\varepsilon^{-2}}$ iteration-complexity to achieve a stationary point in expectation and estimate the total number of stochastic oracle calls for both function value and its Jacobian, where $\varepsilon$ is a desired accuracy. In the finite sum case, we also estimate $\BigO{\varepsilon^{-2}}$ iteration-complexity and the total oracle calls with high probability. To our best knowledge, this is the first time such global stochastic oracle complexity is established for stochastic Gauss-Newton methods. Finally, we illustrate our theoretical results via two numerical examples on both synthetic and real datasets.

Cite this Paper

BibTeX
@InProceedings{pmlr-v119-tran-dinh20a, title = {Stochastic {G}auss-{N}ewton Algorithms for Nonconvex Compositional Optimization}, author = {Tran-Dinh, Quoc and Pham, Nhan and Nguyen, Lam}, booktitle = {Proceedings of the 37th International Conference on Machine Learning}, pages = {9572--9582}, year = {2020}, editor = {III, Hal Daumé and Singh, Aarti}, volume = {119}, series = {Proceedings of Machine Learning Research}, month = {13--18 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v119/tran-dinh20a/tran-dinh20a.pdf}, url = {https://proceedings.mlr.press/v119/tran-dinh20a.html}, abstract = {We develop two new stochastic Gauss-Newton algorithms for solving a class of non-convex stochastic compositional optimization problems frequently arising in practice. We consider both the expectation and finite-sum settings under standard assumptions, and use both classical stochastic and SARAH estimators for approximating function values and Jacobians. In the expectation case, we establish $\BigO{\varepsilon^{-2}}$ iteration-complexity to achieve a stationary point in expectation and estimate the total number of stochastic oracle calls for both function value and its Jacobian, where $\varepsilon$ is a desired accuracy. In the finite sum case, we also estimate $\BigO{\varepsilon^{-2}}$ iteration-complexity and the total oracle calls with high probability. To our best knowledge, this is the first time such global stochastic oracle complexity is established for stochastic Gauss-Newton methods. Finally, we illustrate our theoretical results via two numerical examples on both synthetic and real datasets.} }
Endnote
%0 Conference Paper %T Stochastic Gauss-Newton Algorithms for Nonconvex Compositional Optimization %A Quoc Tran-Dinh %A Nhan Pham %A Lam Nguyen %B Proceedings of the 37th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2020 %E Hal Daumé III %E Aarti Singh %F pmlr-v119-tran-dinh20a %I PMLR %P 9572--9582 %U https://proceedings.mlr.press/v119/tran-dinh20a.html %V 119 %X We develop two new stochastic Gauss-Newton algorithms for solving a class of non-convex stochastic compositional optimization problems frequently arising in practice. We consider both the expectation and finite-sum settings under standard assumptions, and use both classical stochastic and SARAH estimators for approximating function values and Jacobians. In the expectation case, we establish $\BigO{\varepsilon^{-2}}$ iteration-complexity to achieve a stationary point in expectation and estimate the total number of stochastic oracle calls for both function value and its Jacobian, where $\varepsilon$ is a desired accuracy. In the finite sum case, we also estimate $\BigO{\varepsilon^{-2}}$ iteration-complexity and the total oracle calls with high probability. To our best knowledge, this is the first time such global stochastic oracle complexity is established for stochastic Gauss-Newton methods. Finally, we illustrate our theoretical results via two numerical examples on both synthetic and real datasets.
APA
Tran-Dinh, Q., Pham, N. & Nguyen, L.. (2020). Stochastic Gauss-Newton Algorithms for Nonconvex Compositional Optimization. Proceedings of the 37th International Conference on Machine Learning, in Proceedings of Machine Learning Research 119:9572-9582 Available from https://proceedings.mlr.press/v119/tran-dinh20a.html.

Related Material