A Stochastic Levenberg-Marquardt Method Using Random Models with Application to Data Assimilation
El Houcine Bergou, Youssef Diouane, Vyacheslav Kungurtsev, Clément W. Royer · arXiv (Cornell University) · 2018
Globally convergent variants of the Gauss-Newton algorithm are often the preferred methods to tackle nonlinear least squares problems. Among such frameworks, the Levenberg-Marquardt and the trust-region methods are two well-established paradigms, and their similarities have often enabled to derive similar analyses of these schemes. Both algorithms have indeed been successfully studied when the Gauss-Newton model is replaced by a random model, only accurate with a given probability. Meanwhile, problems where even the objective value is subject to noise have gained interest, driven by the need for efficient methods in fields such as data assimilation. In this paper, we describe a stochastic Levenberg-Marquardt algorithm that can handle noisy objective function values as well as random models, provided sufficient accuracy is achieved in probability. Our method relies on a specific scaling of the regularization parameter, which clarifies further the correspondences between the two classes of methods, and allows us to leverage existing theory for trust-region alorithms. Provided the probability of accurate function estimates and models is sufficiently large, we establish that the proposed algorithm converges globally to a first-order stationary point of the objective function with probability one. Furthermore, we derive a bound the expected number of iterations needed to reach an approximate stationary point. We finally describe an application of our method to variational data assimilation, where stochastic models are computed by the so-called ensemble methods.