Convergence acceleration of ensemble Kalman inversion in nonlinear settings

DOI10.1090/MCOM/3709zbMATH Open1486.49049arXiv1911.02424OpenAlexW2984293866MaRDI QIDQ5070540FDOQ5070540

Authors: Neil K. Chada, Xin Thomson Tong 

Publication date: 13 April 2022

Published in: Mathematics of Computation (Search for Journal in Brave)

Abstract: Many data-science problems can be formulated as an inverse problem, where the parameters are estimated by minimizing a proper loss function. When complicated black-box models are involved, derivative-free optimization tools are often needed. The ensemble Kalman filter (EnKF) is a particle-based derivative-free Bayesian algorithm originally designed for data assimilation. Recently, it has been applied to inverse problems for computational efficiency. The resulting algorithm, known as ensemble Kalman inversion (EKI), involves running an ensemble of particles with EnKF update rules so they can converge to a minimizer. In this article, we investigate EKI convergence in general nonlinear settings. To improve convergence speed and stability, we consider applying EKI with non-constant step-sizes and covariance inflation. We prove that EKI can hit critical points with finite steps in non-convex settings. We further prove that EKI converges to the global minimizer polynomially fast if the loss function is strongly convex. We verify the analysis presented with numerical experiments on two inverse problems.

Full work available at URL: https://arxiv.org/abs/1911.02424

Recommendations

• Gradient flow structure and convergence analysis of the ensemble Kalman inversion for nonlinear forward models
• Continuous Time Limit of the Stochastic Ensemble Kalman Inversion: Strong Convergence Analysis
• Well posedness and convergence analysis of the ensemble Kalman inversion
• Ensemble Kalman inversion: mean-field limit and convergence analysis
• Ensemble Kalman methods for inverse problems

zbMATH Keywords

convergence analysisGauss-Newton methodensemble Kalman inversionTihkonov regularizationnon-constant step-size

Mathematics Subject Classification ID

Numerical optimization and variational techniques (65K10) Convex programming (90C25) Inverse problems in optimal control (49N45) Derivative-free methods and methods using generalized derivatives (90C56)

Cites Work

• Adaptive subgradient methods for online learning and stochastic optimization
• Sequential Monte Carlo Samplers
• Optimization by simulated annealing
• Title not available (Why is that?)
• Introductory lectures on convex optimization. A basic course.
• On the stability of sequential Monte Carlo methods in high dimensions
• Acceleration of Stochastic Approximation by Averaging
• Filtering complex turbulent systems.
• A Stochastic Approximation Method
• Title not available (Why is that?)
• Inverse problems: a Bayesian perspective
• Title not available (Why is that?)
• Convergence rates of convex variational regularization
• Title not available (Why is that?)
• Well-posedness and accuracy of the ensemble Kalman filter in discrete and continuous time
• An introduction to computational stochastic PDEs
• A regularizing Levenberg - Marquardt scheme, with applications to inverse groundwater filtration problems
• Stochastic stability of the discrete-time extended Kalman filter
• Title not available (Why is that?)
• Sequential Monte Carlo methods for high-dimensional inverse problems: a case study for the Navier-Stokes equations
• Incremental Least Squares Methods and the Extended Kalman Filter
• The iterated Kalman filter update as a Gauss-Newton method
• The ensemble Kalman filter for combined state and parameter estimation
• Nonlinear stability of the ensemble Kalman filter with adaptive covariance inflation
• Derivative-free optimization: a review of algorithms and comparison of software implementations
• Approximate Gauss–Newton Methods for Nonlinear Least Squares Problems
• Ensemble Kalman methods for inverse problems
• Solving large-scale PDE-constrained Bayesian inverse problems with Riemann manifold Hamiltonian Monte Carlo
• MAP estimators and their consistency in Bayesian nonparametric inverse problems
• Ensemble filter techniques for intermittent data assimilation - a survey
• Unbiased ensemble square root filters
• Large sample asymptotics for the ensemble Kalman filter
• On the convergence of the ensemble Kalman filter.
• Title not available (Why is that?)
• Performance of ensemble Kalman filters in large dimensions
• Iteratively Regularized Gauss–Newton Method for Nonlinear Inverse Problems with Random Noise
• Parameterizations for ensemble Kalman inversion
• Analysis of the ensemble Kalman filter for inverse problems
• Introduction to uncertainty quantification
• Data Assimilation
• Data assimilation: the Schrödinger perspective
• On the continuous time limit of the ensemble Kalman filter
• The incremental Gauss-Newton algorithm with adaptive stepsize rule
• Performance analysis of local ensemble Kalman filter
• Convergence of the square root ensemble Kalman filter in the large ensemble limit
• A regularizing iterative ensemble Kalman method for PDE-constrained inverse problems
• Probabilistic Forecasting and Bayesian Data Assimilation
• Modern regularization methods for inverse problems
• Kalman-based stochastic gradient method with stop condition and insensitivity to conditioning
• Interacting Langevin diffusions: gradient structure and ensemble Kalman sampler
• Well posedness and convergence analysis of the ensemble Kalman inversion
• On the continuous time limit of ensemble square root filters
• Ensemble Kalman inversion: a derivative-free technique for machine learning tasks
• Tikhonov regularization within ensemble Kalman inversion
• Statistical inference for model parameters in stochastic gradient descent
• Localization for MCMC: sampling high-dimensional posterior distributions with local structure
• Accelerating Metropolis-within-Gibbs sampler with localized computations of differential equations
• Bayesian inversion in resin transfer molding
• Learning rate adaptation in stochastic gradient descent.

Cited In (28)

• Efficient Bayesian physics informed neural networks for inverse problems via ensemble Kalman inversion
• Ensemble Kalman inversion for nonlinear problems: weights, consistency, and variance bounds
• On a Dynamic Variant of the Iteratively Regularized Gauss–Newton Method with Sequential Data
• Ensemble Kalman filter for neural network-based one-shot inversion
• Ensemble Kalman inversion: a derivative-free technique for machine learning tasks
• On the ensemble Kalman inversion under inequality constraints
• A strongly convergent numerical scheme from ensemble Kalman inversion
• Interacting Langevin diffusions: gradient structure and ensemble Kalman sampler
• Ensemble Kalman sampler: mean-field limit and convergence analysis
• Ensemble Kalman inversion: mean-field limit and convergence analysis
• Iterated Kalman methodology for inverse problems
• Gradient flow structure and convergence analysis of the ensemble Kalman inversion for nonlinear forward models
• Convergence analysis of ensemble Kalman inversion: the linear, noisy case
• Hierarchical ensemble Kalman methods with sparsity-promoting generalized gamma hyperpriors
• Ensemble Kalman inversion for general likelihoods
• Adaptive Tikhonov strategies for stochastic ensemble Kalman inversion
• Component-wise iterative ensemble Kalman inversion for static Bayesian models with unknown measurement error covariance
• Localized ensemble Kalman inversion
• Iterative ensemble Kalman methods: a unified perspective with some new variants
• On convergence rates of adaptive ensemble Kalman inversion for linear ill-posed problems
• Parameterizations for ensemble Kalman inversion
• Sequential Kalman tuning of the \(t\)-preconditioned Crank-Nicolson algorithm: efficient, adaptive and gradient-free inference for Bayesian inverse problems
• Tikhonov regularization within ensemble Kalman inversion
• A stabilization of a continuous limit of the ensemble Kalman inversion
• A stochastic iteratively regularized Gauss-Newton method
• Adaptive operator learning for infinite-dimensional Bayesian inverse problems
• Complete Deterministic Dynamics and Spectral Decomposition of the Linear Ensemble Kalman Inversion
• Adaptive Ensemble Kalman Inversion with Statistical Linearization

Uses Software

• EnKF
• KELLEY
• MultiMin
• AdaGrad

This page was built for publication: Convergence acceleration of ensemble Kalman inversion in nonlinear settings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5070540)