A stochastic Levenberg-Marquardt method using random models with complexity results
From MaRDI portal
Publication:5075237
DOI10.1137/20M1366253zbMATH Open1487.49035arXiv1807.02176OpenAlexW3179632780MaRDI QIDQ5075237FDOQ5075237
Authors: Vyacheslav Kungurtsev, C. W. Royer, El Houcine Bergou, Youssef Diouane 
Publication date: 10 May 2022
Published in: SIAM/ASA Journal on Uncertainty Quantification (Search for Journal in Brave)
Abstract: 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 the Gauss-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. In this 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 using deterministic models or noiseless function values. We illustrate the link between our approach and several applications related to inverse problems and machine learning.
Full work available at URL: https://arxiv.org/abs/1807.02176
Recommendations
- Levenberg-Marquardt methods based on probabilistic gradient models and inexact subproblem solution, with application to data assimilation
- Convergence and complexity analysis of a Levenberg-Marquardt algorithm for inverse problems
- A Levenberg-Marquardt method for large nonlinear least-squares problems with dynamic accuracy in functions and gradients
- Levenberg-Marquardt method based on probabilistic Jacobian models for nonlinear equations
- Stochastic optimization using a trust-region method and random models
machine learningdata assimilationrandom modelsLevenberg-Marquardt methodnonlinear least squaresworst-case complexitynoisy functions
Abstract computational complexity for mathematical programming problems (90C60) Numerical methods based on necessary conditions (49M05) Derivative-free methods and methods using generalized derivatives (90C56)
Cites Work
- An Algorithm for Least-Squares Estimation of Nonlinear Parameters
- A method for the solution of certain non-linear problems in least squares
- Nonlinear least squares — the Levenberg algorithm revisited
- Title not available (Why is that?)
- Probability and stochastics.
- Introduction to Derivative-Free Optimization
- Inverse Problem Theory and Methods for Model Parameter Estimation
- The ensemble Kalman filter for combined state and parameter estimation
- Stochastic optimization using a trust-region method and random models
- Convergence of trust-region methods based on probabilistic models
- Stochastic derivative-free optimization using a trust region framework
- A derivative-free algorithm for least-squares minimization
- Title not available (Why is that?)
- Computation of sparse low degree interpolating polynomials and their application to derivative-free optimization
- On the local convergence of a derivative-free algorithm for least-squares minimization
- Ensemble Kalman methods for inverse problems
- Global complexity bound of the Levenberg-Marquardt method
- On the evaluation complexity of cubic regularization methods for potentially rank-deficient nonlinear least-squares problems and its relevance to constrained nonlinear optimization
- Title not available (Why is that?)
- Trust-region methods without using derivatives: worst case complexity and the nonsmooth case
- Optimization methods for large-scale machine learning
- Derivative-free optimization methods
- Convergence and evaluation-complexity analysis of a regularized tensor-Newton method for solving nonlinear least-squares problems
- A Levenberg-Marquardt method for large nonlinear least-squares problems with dynamic accuracy in functions and gradients
- Levenberg-Marquardt methods based on probabilistic gradient models and inexact subproblem solution, with application to data assimilation
- A regularizing iterative ensemble Kalman method for PDE-constrained inverse problems
- Adaptive regularisation for ensemble Kalman inversion
- A derivative-free Gauss-Newton method
- Improving the flexibility and robustness of model-based derivative-free optimization solvers
- Convergence and complexity analysis of a Levenberg-Marquardt algorithm for inverse problems
- Tikhonov regularization within ensemble Kalman inversion
- Complexity and global rates of trust-region methods based on probabilistic models
- A Nonmonotone Matrix-Free Algorithm for Nonlinear Equality-Constrained Least-Squares Problems
Cited In (11)
- A Levenberg-Marquardt method for large nonlinear least-squares problems with dynamic accuracy in functions and gradients
- On the complexity of a stochastic Levenberg-Marquardt method
- Stochastic trust-region algorithm in random subspaces with convergence and expected complexity analyses
- Levenberg-Marquardt methods based on probabilistic gradient models and inexact subproblem solution, with application to data assimilation
- Convergence analysis of a subsampled Levenberg-Marquardt algorithm
- Assessing stochastic algorithms for large scale nonlinear least squares problems using extremal probabilities of linear combinations of gamma random variables
- Complexity analysis of regularization methods for implicitly constrained least squares
- A fully stochastic second-order trust region method
- TREGO: a trust-region framework for efficient global optimization
- A stochastic iteratively regularized Gauss-Newton method
- Adaptive Regularization Algorithms with Inexact Evaluations for Nonconvex Optimization
Uses Software
This page was built for publication: A stochastic Levenberg-Marquardt method using random models with complexity results
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5075237)
