A stochastic Levenberg-Marquardt method using random models with complexity results
Bergou, E. H.; Diouane, Y.; Kungurtsev, V.; Royer, Clément W. (2022), A stochastic Levenberg-Marquardt method using random models with complexity results, SIAM/ASA Journal on Uncertainty Quantification, 10, 1, p. 507-536. 10.1137/20M1366253
TypeArticle accepté pour publication ou publié
External document linkhttps://arxiv.org/abs/1807.02176
Journal nameSIAM/ASA Journal on Uncertainty Quantification
SIAM - Society for Industrial and Applied Mathematics
MetadataShow full item record
Abstract (EN)Globally convergent variants of the Gauss--Newton algorithm are often the methods of choice to tackle nonlinear least-squares problems. Among such frameworks, Levenberg--Marquardt and trust-region methods are two well-established, similar paradigms. Both schemes have been studied when theGauss--Newton model is replaced by a random model that is only accurate with a given probability. Trust-region schemes have also been applied to problems where the objective value is subject to noise: this setting is of particular interest in fields such as data assimilation, where efficient methods that can adapt to noise are needed to account for the intrinsic uncertainty in the input data. Inthis paper, we describe a stochastic Levenberg--Marquardt algorithm that handles noisy objective function values and random models, provided sufficient accuracy is achieved in probability. Our method relies on a specific scaling of the regularization parameter that allows us to leverage existing results for trust-region algorithms. Moreover, we exploit the structure of our objective through the use of a family of stationarity criteria tailored to least-squares problems. Provided the probability of accurate function estimates and models is sufficiently large, we bound the expected number of iterations needed to reach an approximate stationary point, which generalizes results based on usingdeterministic models or noiseless function values. We illustrate the link between our approach and several applications related to inverse problems and machine learning.
Subjects / KeywordsLevenberg--Marquardt method; nonlinear least squares; random models; noisy functions; worst-case complexity; data assimilation; machine learning
Showing items related by title and author.
A nonlinear conjugate gradient method with complexity guarantees and its application to nonconvex regression Chan-Renous-Legoubin, Rémi; Royer, Clément W. (2022) Article accepté pour publication ou publié
Curtis, F. E.; Robinson, D. P.; Royer, Clément; Wright, S. J. (2019) Article accepté pour publication ou publié
A note on the paper, “Ranking irregularities when evaluating alternatives by using some ELECTRE methods”, by Wang and Triantaphyllou, Omega (2008) Figueira, José; Roy, Bernard (2009) Article accepté pour publication ou publié
Mousseau, Vincent; Figueira, José; Naux, Jean-Philippe (2001) Article accepté pour publication ou publié
Discriminating thresholds as a tool to cope with imperfect knowledge in multiple criteria decision aiding: Theoretical results and practical issues Roy, Bernard; Figueira, José; Almeida Dias, Juscelino (2014) Article accepté pour publication ou publié