Stochastic Gauss-Newton Algorithms for Nonconvex Compositional Optimization

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 $\mathcal{O}({\epsilon }^{-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 $\epsilon$ is a desired accuracy. In the finite sum case, we also estimate $\mathcal{O}({\epsilon }^{-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.

arXiv comment32 pages and 8 figures

References in corpus (9)

• Adaptive Primal-Dual Hybrid Gradient Methods for Saddle-Point Problems
• Finite-sum Composition Optimization via Variance Reduced Gradient Descent
• Algorithms for stochastic optimization with functional or expectation constraints
• Unbiased Simulation for Optimizing Stochastic Function Compositions
• Variance Reduced methods for Non-convex Composition Optimization
• Proximal Alternating Penalty Algorithms for Constrained Convex Optimization
• Proximal methods for minimizing the sum of a convex function and a composite function
• Stochastic Variance-Reduced Prox-Linear Algorithms for Nonconvex Composite Optimization
• Katyusha Acceleration for Convex Finite-Sum Compositional Optimization