# Stochastic Gauss-Newton Algorithms for Nonconvex Compositional Optimization

arXiv: https://arxiv.org/abs/2002.07290 · HTML: https://mlsanity.com/paper/2002.07290/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Feb 2020.

## Built on by (most cited first, 10 of 10)

- [A Single-Timescale Method for Stochastic Bilevel Optimization](https://mlsanity.com/paper/2102.04671/) (2021)
- [Tighter Analysis of Alternating Stochastic Gradient Method for Stochastic Nested Problems](https://mlsanity.com/paper/2106.13781/) (2021)
- [Exact Gauss-Newton Optimization for Training Deep Neural Networks](https://mlsanity.com/paper/2405.14402/) (2024)
- [Solving Nonlinear PDEs with Sparse Radial Basis Function Networks](https://mlsanity.com/paper/2505.07765/) (2025)
- [Finite-Sum Optimization: A New Perspective for Convergence to a Global Solution](https://mlsanity.com/paper/2202.03524/) (2022)
- [Efficient algorithms for implementing incremental proximal-point methods](https://mlsanity.com/paper/2205.01457/) (2022)
- [Linearization Algorithms for Fully Composite Optimization](https://mlsanity.com/paper/2302.12808/) (2023)
- [Modified Gauss-Newton Algorithms under Noise](https://mlsanity.com/paper/2305.10634/) (2023)
- [Incremental Gauss-Newton Descent for Machine Learning](https://mlsanity.com/paper/2408.05560/) (2024)
- [Dual Gauss-Newton Directions for Deep Learning](https://mlsanity.com/paper/2308.08886/) (2023)

## Abstract (arXiv)

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 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 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.