Complexity bound of a Levenberg–Marquardt algorithm based on probabilistic Jacobian models

In this paper, we present a Levenberg–Marquardt algorithm for nonlinear equations, where the exact Jacobians are unavailable, but their model approximations can be built in some random fashion. We study the complexity of the algorithm and show that the upper bound of the iteration numbers in expectation to obtain a first order stationary point is \(O(\epsilon ^{-3})\) $O({ϵ}^{-3})$ .