  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}(\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
$\mathcal{O}(\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.
