Stochastic Gauss-Newton Algorithms for Nonconvex Compositional Optimization
This work addresses optimization challenges in machine learning and statistics, but it is incremental as it extends existing Gauss-Newton methods to stochastic settings with new complexity bounds.
The authors tackled nonconvex stochastic compositional optimization problems by developing two stochastic Gauss-Newton algorithms, achieving an O(ε⁻²) iteration complexity for finding stationary points in expectation and with high probability, and establishing the first global stochastic oracle complexity for such methods.
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.